2.1.1 Definitions
B+-tree
- is a structure of blocks linked by pointers
- is anchored by a special block called the root, and bounded by leaves
- has a unique path to each leaf, and all paths are equal length
- stores keys only at leaves, and stores reference values in other,
internal, blocks
- guides key search, via the reference values, from the root to the leaves
block
- is either internal or a leaf, including the root block
- contains at most n entries and one extra pointer for some fixed n
- has no fewer than [n/2] entries, the root excepted
root block
- is a leaf when it is the only block in the tree and will then contain at
least one entry
- must have at least 2 pointers to other blocks when it is internal
internal block
- contains entries consisting of a reference value and a pointer towards
the leaves
- its entries point to data classified as greater than or equal to the
corresponding reference value
- its extra pointer references data classified as less than the block’s
smallest reference value
leaf block
- contains entries consisting of a key value and a pointer to the storage
location of data matching the key
- its extra pointer references the next leaf block in the tree ordering;
leaves linked in this manner are neighbors
prefix compression
Instead of storing the full text of each key, store the length of match
with the previous key (in this block) and the text of the key which
doesn’t match.
suffix compression
In non-leaf blocks, only store enough of the split-key to differentiate
the two sequential blocks at the lower level.