B+ tree
B+ tree
A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,[1] typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this type of tree for metadata indexing; BFS also uses B+ trees for storing directories. NTFS uses B+ trees for directory and security-related metadata indexing. EXT4 uses extent trees (a modified B+ tree data structure) for file extent indexing.[3] Relational database management systems such as IBM DB2,[4] Informix,[4] Microsoft SQL Server,[4] Oracle 8,[4] Sybase ASE,[4] and SQLite[5] support this type of tree for table indices. Key–value database management systems such as CouchDB[6] and Tokyo Cabinet[7] support this type of tree for data access.
Overview
| Node Type | Children Type | Min Number of Children | Max Number of Children | Example | Example |
|---|---|---|---|---|---|
| Root Node (when it is the only node in the tree) | Records | 1 | 1–6 | 1–99 | |
| Root Node | Internal Nodes or Leaf Nodes | 2 | b | 2–7 | 2–100 |
| Internal Node | Internal Nodes or Leaf Nodes | b | 4–7 | 50–100 | |
| Leaf Node | Records | 4–7 | 50–100 |
Algorithms
Search
The root of a B+ Tree represents the whole range of values in the tree, where every internal node is a subinterval.
This pseudocode assumes that no duplicates are allowed.
Prefix key compression
It is important to increase fan-out, as this allows to direct searches to the leaf level more efficiently.
Index Entries are only to 'direct traffic', thus we can compress them.
Insertion
Perform a search to determine what bucket the new record should go into.
If the bucket is not full (at most entries after the insertion), add the record.
Otherwise, before inserting the new record split the bucket. original node has ⎡(L+1)/2⎤ items new node has ⎣(L+1)/2⎦ items Move ⎡(L+1)/2⎤-th key to the parent, and insert the new node to the parent. Repeat until a parent is found that need not split.
If the root splits, treat it as if it has an empty parent and split as outline above.
B-trees grow at the root and not at the leaves.[1]
Bulk-loading
Given a collection of data records, we want to create a B+ tree index on some key field. One approach is to insert each record into an empty tree. However, it is quite expensive, because each entry requires us to start from the root and go down to the appropriate leaf page. An efficient alternative is to use bulk-loading.
The first step is to sort the data entries according to a search key in ascending order.
We allocate an empty page to serve as the root, and insert a pointer to the first page of entries into it.
When the root is full, we split the root, and create a new root page.
Keep inserting entries to the right most index page just above the leaf level, until all entries are indexed.
Note :
when the right-most index page above the leaf level fills up, it is split;
this action may, in turn, cause a split of the right-most index page on step closer to the root;
splits only occur on the right-most path from the root to the leaf level.[8]
Characteristics
For a b-order B+ tree with h levels of index:
The maximum number of records stored is
The minimum number of records stored is
The minimum number of keys is
The maximum number of keys is
The space required to store the tree is
Inserting a record requires operations
Finding a record requires operations
Removing a (previously located) record requires operations
Performing a range query with k elements occurring within the range requires operations
Implementation
The leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient (though the aforementioned upper bound can be achieved even without this addition). This does not substantially increase space consumption or maintenance on the tree. This illustrates one of the significant advantages of a B+tree over a B-tree; in a B-tree, since not all keys are present in the leaves, such an ordered linked list cannot be constructed. A B+tree is thus particularly useful as a database system index, where the data typically resides on disk, as it allows the B+tree to actually provide an efficient structure for housing the data itself (this is described in[4] [] as index structure "Alternative 1").
If nodes of the B+ tree are organized as arrays of elements, then it may take a considerable time to insert or delete an element as half of the array will need to be shifted on average. To overcome this problem, elements inside a node can be organized in a binary tree or a B+ tree instead of an array.
B+ trees can also be used for data stored in RAM. In this case a reasonable choice for block size would be the size of processor's cache line.
All the above compression techniques have some drawbacks. First, a full block must be decompressed to extract a single element. One technique to overcome this problem is to divide each block into sub-blocks and compress them separately. In this case searching or inserting an element will only need to decompress or compress a sub-block instead of a full block. Another drawback of compression techniques is that the number of stored elements may vary considerably from a block to another depending on how well the elements are compressed inside each block.
History
The B tree was first described in the paper Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173–189 (1972) by Rudolf Bayer and Edward M. McCreight. There is no single paper introducing the B+ tree concept. Instead, the notion of maintaining all data in leaf nodes is repeatedly brought up as an interesting variant. An early survey of B trees also covering B+ trees is Douglas Comer.[9] Comer notes that the B+ tree was used in IBM's VSAM data access software and he refers to an IBM published article from 1973.
See also
Binary search tree
B-tree
Divide and conquer algorithm