B+树
2019-12-11 本文已影响0人
nzdxwl
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]（向上取整）个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树与B树的不同：
Difference between B Tree and B+ Tree
| B Tree | B+ Tree | |
|---|---|---|
| Short web descriptions | A B tree is an organizational structure for information storage and retrieval in the form of a tree in which all terminal nodes are at the same distance from the base, and all non-terminal nodes have between n and 2 n sub-trees or pointers (where n is an integer). | B+ tree is an n-array tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. |
| Also known as | Balanced tree. | B plus tree. |
| Space | O(n) | O(n) |
| Search | O(log n) | O(logb n) |
| Insert | O(log n) | O(logb n) |
| Delete | O(log n) | O(logb n) |
| Storage | In a B tree, search keys and data stored in internal or leaf nodes. | In a B+ tree, data stored only in leaf nodes. |
| Data | The leaf nodes of the tree store pointers to records rather than actual records. | The leaf nodes of the tree stores the actual record rather than pointers to records. |
| Space | These trees waste space | There trees do not waste space. |
| Function of leaf nodes | In B tree, the leaf node cannot store using linked list. | In B+ tree, leaf node data are ordered in a sequential linked list. |
| Searching | Here, searching becomes difficult in B- tree as data cannot be found in the leaf node. | Here, searching of any data in a B+ tree is very easy because all data is found in leaf nodes. |
| Search accessibility | Here in B tree the search is not that easy as compared to a B+ tree. | Here in B+ tree the searching becomes easy. |
| Redundant key | They do not store redundant search key. | They store redundant search key. |
| Applications | They are an older version and are not that advantageous as compared to the B+ trees. | Many database system implementers prefer the structural simplicity of a B+ tree. |
