Editing B-tree (section)

===Variants===
The term '''B-tree''' may refer to a specific design or a general class of designs. In the narrow sense, a B-tree stores keys in its internal nodes but need not store those keys in the records at the leaves. The general class includes variations such as the [[B+ tree]], the B<sup>*</sup> tree and the B<sup>*+</sup> tree.
* In the [[B+ tree]], the internal nodes do not store any pointers to records, thus all pointers to records are stored in the leaf nodes. In addition, a leaf node may include a pointer to the next leaf node to speed up sequential access.{{sfn|Comer|1979}} Because B+ tree internal nodes have fewer pointers, each node can hold more keys, causing the tree to be shallower and thus faster to search.
* The B<sup>*</sup> tree balances more neighboring internal nodes to keep the internal nodes more densely packed.{{sfn|Comer|1979}} This variant ensures non-root nodes are at least 2/3 full instead of 1/2.{{sfn|Knuth|1998|p=488}} As the most costly part of operation of inserting the node in B-tree is splitting the node, B<sup>*</sup>-trees are created to postpone splitting operation as long as they can.<ref name="Milo">{{cite book |last=Tomašević |first=Milo |title=Algorithms and Data Structures |year=2008 |publisher=Akademska misao |location=Belgrade, Serbia |isbn=978-86-7466-328-8 |pages=274–275}}</ref> To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with a node next to it. This spill operation is less costly to do than split, because it requires only shifting the keys between existing nodes, not allocating memory for a new one.{{r|Milo}} For inserting, first it is checked whether the node has some free space in it, and if so, the new key is just inserted in the node. However, if the node is full (it has {{math|''m'' − 1}} keys, where {{mvar| m}} is the order of the tree as maximum number of pointers to subtrees from one node), it needs to be checked whether the right sibling exists and has some free space. If the right sibling has {{math|''j'' < ''m'' − 1}} keys, then keys are redistributed between the two sibling nodes as evenly as possible. For this purpose, {{mvar|''m'' &minus; 1}} keys from the current node, the new key inserted, one key from the parent node and {{mvar|j}} keys from the sibling node are seen as an ordered array of {{math|''m'' + ''j'' + 1}} keys. The array becomes split by half, so that {{math|{{floor|(''m'' + ''j'' + 1)/2}}}} lowest keys stay in the current node, the next (middle) key is inserted in the parent and the rest go to the right sibling.{{r|Milo}} (The newly inserted key might end up in any of the three places.) The situation when right sibling is full, and left isn't is analogous.{{r|Milo}} When both the sibling nodes are full, then the two nodes (current node and a sibling) are split into three and one more key is shifted up the tree, to the parent node.{{r|Milo}} If the parent is full, then spill/split operation propagates towards the root node.{{r|Milo}} Deleting nodes is somewhat more complex than inserting however.
* The B<sup>*+</sup> tree combines the main [[B+ tree]] and B<sup>*</sup> tree features together.<ref>{{Cite journal|language=en|url=https://ispranproceedings.elpub.ru/jour/article/view/1188|title=SQLite RDBMS Extension for Data Indexing Using B-tree Modifications|author=Rigin A. M., Shershakov S. A.|journal=Proceedings of the Institute for System Programming of the RAS|date=2019-09-10|volume=31 |issue=3 |pages=203–216 |publisher=Institute for System Programming of the RAS (ISP RAS)|doi=10.15514/ispras-2019-31(3)-16|s2cid=203144646 |access-date=2021-08-29|doi-access=free}}</ref>
* B-trees can be turned into [[order statistic tree]]s to allow rapid searches for the Nth record in key order, or counting the number of records between any two records, and various other related operations.<ref>{{Cite web |title=Counted B-Trees |url=https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html |access-date=2024-12-27 |website=www.chiark.greenend.org.uk}}</ref>