Summary
B-trees and B+ trees are used usually when the index grows so large that it can not be economically held in memory.
B-Tree of Order m
It is a multilevel index tree with the following properties:
- Every node has a maximum of
m descendants.
- Every node except the root has at least
⌈m/2⌉ descendants.
- The root has at least two descendants (unless it is a leaf).
- All of the leaves appear on the same level.
The major weakness of this strategy is the lack of organization of the data file, resulting in an excessive amount of seeking for sequential access.
B+ Tree
A B+ tree consists of a sequence set of records that are ordered sequentially by key, along with an index set that provides indexed access to the records.
All of the records are stored in the sequence set.
The index set, which is used only as a finding aid to the blocks in the sequence set, is managed as a B-tree.
B+ trees has two advantages over B-trees:
- The sequence set can be processed in a truly linear, sequential way.
- The index is built with a single key per block of data records instead of one key per data record.
The size of the lowest-level index is reduced by the blocking factor of the data file.
Simple Prefix B+ Tree
It is a B+ tree in which the index set is made up of shortest separators that are simple prefixes.
The index is smaller and hence shallower than the index of B+ tree because the separators in the index set are smaller and more of them can be fitted into a block to obtain a higher branching factor out of the block.