A B+ Tree is a variant of the B-Tree that stores a copy of every key at the leaf/lowest level. Like the B-Tree, it is a self-balancing, abstract, non-linear data structure.
%%🖋 Edit in Excalidraw, and the light exported image%%
Properties
A B+ Tree has the same properties of a B-Tree:
AND:
- All data pointers (that is, not node pointers, but pointers to actual data the tree is storing) is only on the lowest, leaf level.
- A parent key will have a copy of itself in the lowest level
- Every key can be found in the lowest level
ADT Signature
name: B+ Tree
Time Complexity Analysis
Basic Operation:
| Operation | Worst Case (WC) | Best Case (BC) | Average Case (AC) | Case descriptions |
|---|---|---|---|---|