B-tree of order n is an order-n multiway tree in which each non-root node contains

A B-tree of order n is an order-n multiway tree in which each non-root node contains between ⌈n/2⌉ and n children. Each node in the B-tree contains at most n-1 keys with the keys in ascending order.

Here are the steps to understand a B-tree of order n:

1. Start with an empty root. The B-tree is of order n.

2. Insert keys. If the root node is full (contains n-1 keys), split it. The middle key moves up and becomes the root. The remaining keys are divided between two new nodes, each becoming a child of the new root.

3. Continue inserting keys. If a non-root node is full upon insertion, split it. The middle key moves up to the parent node. If the parent node is full, repeat the split process.

4. If a key is to be deleted, there are several cases to consider:

   • If the key k is in node x and x is a leaf, delete the key k from x.
   • If the key k is in node x and x is an internal node, there are several cases to consider.
     • If the child y that precedes k in node x has at least t keys, then find the predecessor k0 of k in the sub-tree rooted at y. Recursively delete k0, and replace k by k0 in x. (We can find and delete k0 and replace k by k0 in a single downward pass.)
     • If y has fewer than t keys, then, symmetrically, if the child z that follows k in node x has at least t keys, then find the successor k0 of k in the sub-tree rooted at z. Recursively delete k0, and replace k by k0 in x. We can find and delete k0 and replace k by k0 in a single downward pass.
     • Otherwise, if both y and z have only t-1 keys, merge k and all of z into y, so that x loses both k and the pointer to z, and y now contains 2t-1 keys. Then free z and recursively delete k from y.

5. The B-tree properties ensure that the tree remains balanced, with every leaf node being at the same depth. This makes B-trees useful for large databases stored on disk, as the number of disk accesses is minimized.