B+ tree
Encyclopedia : B : BT : BTR : B+ tree
In computer science, a B+ tree is a type of tree data structure. It represents sorted data in a way that allows for efficient insertion and removal of elements. It is a dynamic, multilevel index with maximum and minimum bounds on the number of keys in each node.
A B+ tree is a variation on a B-tree. In a B+ tree, in contrast to a B-tree, all data is saved in the leaves. Internal nodes contain only keys and tree pointers. All leaves are at the same lowest level. Leaf nodes are also linked together as a linked list to make range queries easy.
The maximum number of pointers in a record is called the order of the B+ tree.
The minimum number of keys per record is 1/2 of the maximum number of keys. For example, if the order of a B+ tree is n+1, each node (except for the root) must have between n+1/2 and n keys. If n is an even number the minimum number of keys can be either (n/2)-0.5 or (n/2)+0.5 but it must be the same in the whole tree.
The number of keys that may be indexed using a B+ tree is a function of the order of the tree and its height.
For a n-order B+ tree with a height of h:
- maximum number of keys is [n^h]
- minimum number of keys is [2(n/2)^.]
External links
- http://www.seanster.com/BplusTree/BplusTree.html
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.