Deletion & Properties of B+ Trees
Deleting Values
To delete a value/pointer pair:
- Find the leaf that should contain the value.
- If not there then we are done.
- Remove the value/pointer pair.
- Let the current node $C$.
-
Let $x$ be:
\[x= \begin{cases} 2 & \text{if } C\text{ is root}\\ \lceil\frac{n+1}2\rceil & \text{if } C \text{ id internal node}\\ \lfloor\frac{n+1} 2\rfloor & \text{if } C \text{ is leaf} \end{cases}\]- If $C$ has above $x$ pointers - Fix ancestors (if necessary) and you are done.
- if $C$ is the root but not a leaf - Remove it (and let the child of the root be the new root).
-
Otherwise, check if an adjacent node has at least $x+1$ pointers.
A node is adjacent to another if they are at the same depth and their common ancestor has no descendant at that depth between them.
- If so - Take one, fix ancestors (if necessary) and you are done.
- Otherwise - Merge with sibling and go to line 3 with the parent as the current node.
The running time is:
\[O(h\times\log_2n)\]where $h$ is the height of the B+ tree.
The real running time is:
\[O(h\times D)\]where $D$ is the time for a disk operation.
Properties of B+ Tree Indexes
-
Fast lookups, insertions and deletions:
\[\begin{aligned} O(h\times\log_2n) & = O(\log_nN\times\log_2n)\\ & = O(\log_2N) \end{aligned}\]where $n\approx B$ and $h$ is the height of the tree.
- They remain balanced when modified.
- Huge capacity, even with height 3 if blocks are large enough:
- Block Size - 16K
- Values Stores in Index - 4 bytes
- Pointers - 8 bytes
- Largest $n$ so that each B+ tree node fits into a block is 1364.
- B+ trees with height 3 can store $>n^3=2.5\times 10^9$ values.
- Can be implemented efficiently with respect to number of disk accesses:
- Number of disk accesses is typically $\approx 2+h$, where $h$ is the height of the B+ tree.
- Most of the B+ tree can be kept in memory:
- Specifically the upper levels.