Advantages of B-Trees
- The desired record is found at a shallow depth (few disk accesses).
A tree with 256 keys per node can index millions of records in 3 steps
or 1 disk access (keeping the root node and next level in memory).
- In general, there are many more searches than insertions.
- Since a node can have a wide range of children, m / 2 to m,
an insert or delete will rarely go outside this range.
It is rarely necessary to rebalance the tree.
- Inserting or deleting an item within a node is O(blocksize),
since on average half the block must be moved, but this is fast compared
to a disk access.
- Rebalancing the tree on insertion is easy: if a node would become
over-full, break it into two half-nodes, and insert the new key and pointer
into its parent. Or, if a leaf node becomes over-full, see if a
neighbor node can take some extra children.
- In many cases, rebalancing the tree on deletion can simply be
ignored: it only wastes disk space, which is cheap.