| B+ Tree |
Website Links For Tree |
Information AboutB+ Tree |
|
A B+ tree is a variation on a B-tree . In a B+ tree, in contrast to a B tree, all data are 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 keys 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'', each node (except for the root) must have between ''n''/2 and ''n'' keys. 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'':
The B+ tree was first described in the paper " Rudolf Bayer , Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)". SAMPLE IMPLEMENTATION IN C++ This code snippet has been tested under Linux on a 32- Bit X86 computer. Deletion of keys has not been implemented yet. It can be done quite easily in a lazy way with an Amortized Cost of '' O (log n)'', by rebuilding the tree from scratch every time that there are as many deleted keys as non-deleted keys. The rebuilding can be done in ''O(n)'' time, so its amortized cost is only ''O(1)''. This approach, however, would not be appropriate for Real Time Systems . The implementation uses the Boost Library to have Compile -time assertions and efficient memory allocation. The latter could be done with the new operator instead, resulting in some performance penalty. |
|
|