View source for B-tree

{{Short description|A self-balancing, tree-based data structure, that allows read/write access in logarithmic time}}
{{Distinguish|Binary tree|B+ tree}}
{{Infobox data structure
| name = B-tree
| type = [[Tree (data structure)]]
| invented_by = [[Rudolf Bayer]], [[Edward M. McCreight]]
| invented_year = 1970<ref name="bayer-mccreight-1970">{{Cite conference|last1=Bayer|first1=R.|last2=McCreight|first2=E.|book-title=Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70|date=July 1970|title=Organization and maintenance of large ordered indices|page=107|url=https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf|publisher=Boeing Scientific Research Laboratories|doi=10.1145/1734663.1734671|s2cid=26930249}}</ref>
| space_avg = O(''n'')
| space_worst = O(''n'')
| search_avg = O(log ''n'')
| search_worst = O(log ''n'')
| insert_avg = O(log ''n'')
| insert_worst = O(log ''n'')
| delete_avg = O(log ''n'')
| delete_worst = O(log ''n'')
}}
In [[computer science]], a '''B-tree''' is a self-balancing [[tree data structure]] that maintains sorted data and allows searches, sequential access, insertions, and deletions in [[logarithmic time]]. The B-tree generalizes the [[binary search tree]], allowing for [[Node (computer science)|nodes]] with more than two children.{{sfn|Comer|1979}} Unlike other [[self-balancing binary search tree]]s, the B-tree is well suited for storage systems that read and write relatively large [[Block (data storage)|blocks of data]], such as [[database]]s and [[file system]]s.
==History==
B-trees were invented by [[Rudolf Bayer]] and [[Edward M. McCreight]] while working at [[Boeing|Boeing Research Labs]], for the purpose of efficiently managing index pages for large random-access files. The basic assumption was that indices would be so voluminous that only small chunks of the tree could fit in main memory. Bayer and McCreight's paper ''Organization and maintenance of large ordered indices''<ref name="bayer-mccreight-1970"/> was first circulated in July 1970 and later published in ''[[Acta Informatica]]''.{{sfn|Bayer|McCreight|1972}}
Bayer and McCreight never explained what, if anything, the ''B'' stands for; ''Boeing'', ''balanced'', ''between'', ''broad'', ''bushy'', and ''Bayer'' have been suggested.{{sfn|Comer|1979|p=123 footnote 1}}<ref name=herrenalb/><ref>{{cite web |url=http://scpd.stanford.edu/knuth/index.jsp |title=Stanford Center for Professional Development |website=scpd.stanford.edu |access-date=2011-01-16 |archive-url=https://web.archive.org/web/20140604193847/http://scpd.stanford.edu/knuth/index.jsp |archive-date=2014-06-04 |url-status=dead}}</ref> McCreight has said that "the more you think about what the B in B-trees means, the better you understand B-trees".<ref name=herrenalb>{{cite web |url=https://vimeo.com/73481096 |title=4- Edward M McCreight |first=Peter G. |last=Weiner |date=30 August 2013 |via=Vimeo}}</ref>
==Definition==
According to [[Donald Knuth|Knuth]]'s definition, a B-tree of order ''m'' is a tree which satisfies the following properties:{{sfn|Knuth|1998|p=483}}
# Every node has at most ''m'' children.
# Every node, except for the root and the leaves, has at least ⌈''m''/2⌉ children.
# The root node has at least two children unless it is a leaf.
# All leaves appear on the same level.
# A non-leaf node with ''k'' children contains ''k''&minus;1 keys.
Each internal node's keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: ''a''<sub>1</sub> and ''a''<sub>2</sub>. All values in the leftmost subtree will be less than ''a''<sub>1</sub>, all values in the middle subtree will be between ''a''<sub>1</sub> and ''a''<sub>2</sub>, and all values in the rightmost subtree will be greater than ''a''<sub>2</sub>.
;Internal nodes
: Internal nodes (also known as [[Tree (data structure)#Terminology|inner node]]s) are all nodes except for leaf nodes and the root node. They are usually represented as an ordered set of elements and child pointers. Every internal node contains a '''maximum''' of ''U'' children and a '''minimum''' of ''L'' children. Thus, the number of elements is always 1 less than the number of child pointers (the number of elements is between ''L''−1 and ''U''−1). ''U'' must be either 2''L'' or 2''L''−1; therefore each internal node is at least half full. The relationship between ''U'' and ''L'' implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there's room to push one element up into the parent). These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.
;The root node
: The root node's number of children has the same upper limit as internal nodes, but has no lower limit. For example, when there are fewer than ''L''−1 elements in the entire tree, the root will be the only node in the tree with no children at all.
;Leaf nodes
: In Knuth's terminology, the "leaf" nodes are the actual data objects / chunks. The internal nodes that are one level above these leaves are what would be called the "leaves" by other authors: these nodes only store keys (at most ''m''-1, and at least ''m''/2-1 if they are not the root) and pointers (one for each key) to nodes carrying the data objects / chunks.
A B-tree of depth ''n''+1 can hold about ''U'' times as many items as a B-tree of depth ''n'', but the cost of search, insert, and delete operations grows with the depth of the tree. As with any balanced tree, the cost grows much more slowly than the number of elements.
Some balanced trees store values only at leaf nodes, and use different kinds of nodes for leaf nodes and internal nodes. B-trees keep values in every node in the tree except leaf nodes.
===Differences in terminology===
The literature on B-trees is not uniform in its terminology.{{sfn|Folk|Zoellick|1992|p=362}}
Bayer and McCreight (1972),{{sfn|Bayer|McCreight|1972}} Comer (1979),{{sfn|Comer|1979}} and others define the '''order''' of B-tree as the minimum number of keys in a non-root node.  Folk and Zoellick {{sfn|Folk|Zoellick|1992|p=363}} points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys. Knuth (1998) avoids the problem by defining the '''order''' to be the maximum number of children (which is one more than the maximum number of keys).{{sfn|Knuth|1998|p=483}}
The term '''leaf''' is also inconsistent. Bayer and McCreight (1972){{sfn|Bayer|McCreight|1972}} considered the leaf level to be the lowest level of keys, but Knuth considered the leaf level to be one level below the lowest keys.{{sfn|Folk|Zoellick|1992|p=363}} There are many possible implementation choices. In some designs, the leaves may hold the entire data record; in other designs, the leaves may only hold pointers to the data record. Those choices are not fundamental to the idea of a B-tree.<ref>{{Harvtxt|Bayer|McCreight|1972}} avoided the issue by saying an index element is a (physically adjacent) pair of (''x'',&nbsp;''a'') where ''x'' is the key, and ''a'' is some associated information. The associated information might be a pointer to a record or records in a random access, but what it was didn't really matter. {{Harvtxt|Bayer|McCreight|1972}} states, "For this paper the associated information is of no further interest."</ref>
For simplicity, most authors assume there are a fixed number of keys that fit in a node. The basic assumption is the key size is fixed and the node size is fixed. In practice, variable length keys may be employed.{{sfn|Folk|Zoellick|1992|p=379}}
==Informal description==
[[File:B-tree.svg|thumb|400px|right|A B-tree {{Harv|Bayer|McCreight|1972}} of order 5 {{Harv|Knuth|1998}}.]]
===Node structure===
As with other trees, B-trees can be represented as a collection of three types of nodes: ''root'', ''internal'' (a.k.a. interior), and ''leaf''.
Note the following variable definitions:
* ''{{mvar|K}}'': Maximum number of potential search keys for each node in a B-tree. (this value is constant over the entire tree).
* <math>pt_i</math>: The pointer to a child node which starts a sub-tree.
* <math>pr_i</math>: The pointer to a record which stores the data.
* <math>k_i</math>: The search key at the zero-based node index <math>i</math>.
In B-trees, the following properties are maintained for these nodes:
* If <math display="inline">k_i</math> exists in any node in a B+ tree, then <math>k_{i-1}</math> exists in that node where <math>i \ge 1</math>.
* All leaf nodes have the same number of ancestors (i.e., they are all at the same depth).
Each internal node in a B-tree has the following format:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Internal node structure
!pt<sub>0</sub>
!k<sub>0</sub>
!pt<sub>1</sub>
!pr<sub>0</sub>
!k<sub>1</sub>
!pt<sub>2</sub>
!pr<sub>1</sub>
!...
!k<sub>K-1</sub>
!pt<sub>K</sub>
!pr<sub>K-1</sub>
|}
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Internal node pointer structure
!<math>   pt _0</math> when <math>k_0</math> exists
!<math>pt_i</math> when <math>k_{i-1}</math> and <math>k_i</math> exist
!<math>pt_i</math> when <math>k_{i-1}</math> exists, and <math>k_i</math> does not exist
!<math>pt_i</math> when <math>k_{i-1}</math> and <math>k_i</math> do not exist
!<math>pr_i</math> when <math>k_i</math> exists
!<math>pr_i</math> when <math>k_i</math> does not exist
|-
|Points to subtree in which all search keys are less than <math>k_0</math>.
|Points to subtree in which all search keys are greater than <math>k_{i-1}</math> and are less than <math>k_i</math>.
|Points to subtree in which all search keys are greater than <math>k_{i-1}</math>.
|Here, <math>pt_i</math> is empty.
|Points to a record with a value equal to <math>k_i</math>.
|Here, <math>pr_i</math> is empty.
|}
Each leaf node in a B-tree has the following format:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Leaf node structure
!pr<sub>0</sub>
!k<sub>0</sub>
!pr<sub>1</sub>
!k<sub>1</sub>
!...
!pr<sub>K-1</sub>
!k<sub>K-1</sub>
|}
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+Leaf node pointer structure
!<math>pr_i</math> when <math>k_i</math> exists
!<math>pr_i</math> when <math>k_i</math> does not exist
|-
|Points to a record with a value equal to <math>k_i</math>.
|Here, <math>pr_i</math> is empty.
|}
The node bounds are summarized in the table below:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
!Node type
!Min number<br/> of keys
!Max number<br/> of keys
!Min number<br/> of child nodes
!Max number<br/> of child nodes
|-
|Root node when it is a leaf node
|0
|<math> K </math>
|0
|0
|-
|Root node when it is an internal node
|1
|<math> K </math>
|2<ref name="Navathe2">{{cite book |last=Navathe |first=Ramez Elmasri, Shamkant B. |title=Fundamentals of database systems |publisher=Pearson Education |year=2010 |isbn=9780136086208 |edition=6th |location=Upper Saddle River, N.J. |pages=652–660}}</ref>
|<math> K + 1 </math>
|-
|Internal node
|<math> \lfloor K/2 \rfloor </math>
|<math> K </math>
|<math> \lceil (K + 1)/2 \rceil </math> <math>  \equiv \lfloor K / 2 \rfloor + 1 </math>
|<math> K + 1 </math>
|-
|Leaf node
|<math>  \lceil K / 2 \rceil </math>
|<math> K </math>
|0
|0
|}
===Insertion and deletion===
In order to maintain the predefined range of child nodes, internal nodes may be joined or split.
Usually, the number of keys is chosen to vary between <math>d</math> and <math>2d</math>, where <math>d</math> is the minimum number of keys, and <math>d+1</math> is the minimum [[Outdegree#Indegree and outdegree|degree]] or [[branching factor]] of the tree. The factor of 2 will guarantee that nodes can be split or combined.
If an internal node has <math>2d</math> keys, then adding a key to that node can be accomplished by splitting the hypothetical <math>2d+1</math> key node into two <math>d</math> key nodes and moving the key that would have been in the middle to the parent node. Each split node has the required minimum number of keys. Similarly, if an internal node and its neighbor each have <math>d</math> keys, then a key may be deleted from the internal node by combining it with its neighbor. Deleting the key would make the internal node have <math>d-1</math> keys; joining the neighbor would add <math>d</math> keys plus one more key brought down from the neighbor's parent. The result is an entirely full node of <math>2d</math> keys.
A B-tree is kept balanced after insertion by splitting a would-be overfilled node, of <math>2d+1</math> keys, into two <math>d</math>-key siblings and inserting the mid-value key into the parent. Depth only increases when the root is split, maintaining balance. Similarly, a B-tree is kept balanced after deletion by merging or redistributing keys among siblings to maintain the <math>d</math>-key minimum for non-root nodes. A merger reduces the number of keys in the parent potentially forcing it to merge or redistribute keys with its siblings, and so on. The only change in depth occurs when the root has two children, of <math>d</math> and (transitionally) <math>d-1</math> keys, in which case the two siblings and parent are merged, reducing the depth by one.
This depth will increase slowly as elements are added to the tree, but an increase in the overall depth is infrequent, and results in all leaf nodes being one more node farther away from the root.
===Comparison to other trees===
Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full.
B-trees have substantial advantages over alternative implementations when the time to access the data of a node greatly exceeds the time spent processing that data, because then the cost of accessing the node may be amortized over multiple operations within the node. This usually occurs when the node data are in [[secondary storage]] such as [[hard drive|disk drives]]. By maximizing the number of keys within each [[internal node]], the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing of the tree occurs less often. The maximum number of child nodes depends on the information that must be stored for each child node and the size of a full [[Block (data storage)|disk block]] or an analogous size in secondary storage. While 2–3 B-trees are easier to explain, practical B-trees using secondary storage need a large number of child nodes to improve performance.
===Variants===
The term '''B-tree''' may refer to a specific design or it may refer to 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'' - 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>[http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html Counted B-Trees], retrieved 2010-01-25</ref>
==B-tree usage in databases==
{{Tone|section|date=May 2022}}
===Time to search a sorted file===
Sorting and searching algorithms can be characterized by the number of comparison operations that must be performed using [[Big O notation|order notation]]. A [[binary search]] of a sorted table with {{mvar|N}} records, for example, can be done in roughly {{math|⌈ log<sub>2</sub> ''N'' ⌉}} comparisons. If the table had 1,000,000 records, then a specific record could be located with at most 20 comparisons: {{math|1=⌈ log<sub>2</sub> (1,000,000) ⌉ = 20}}.
Large databases have historically been kept on disk drives. The time to read a record on a disk drive far exceeds the time needed to compare keys once the record is available due to [[seek time]] and a rotational delay. The seek time may be 0 to 20 or more milliseconds, and the rotational delay averages about half the rotation period. For a 7200 RPM drive, the rotation period is 8.33 milliseconds. For a drive such as the Seagate ST3500320NS, the track-to-track seek time is 0.8 milliseconds and the average reading seek time is 8.5 milliseconds.<ref>{{cite book |publisher=Seagate Technology LLC |title=Product Manual: Barracuda ES.2 Serial ATA, Rev. F., publication 100468393 |date=2008 |url=http://www.seagate.com/staticfiles/support/disc/manuals/NL35%20Series%20&%20BC%20ES%20Series/Barracuda%20ES.2%20Series/100468393f.pdf |page=6}}</ref> For simplicity, assume reading from disk takes about 10 milliseconds.
The time to locate one record out of a million in the example above would take 20 disk reads times 10 milliseconds per disk read, which is 0.2 seconds.
The search time is reduced because individual records are grouped together in a disk '''block'''. A disk block might be 16 kilobytes. If each record is 160 bytes, then 100 records could be stored in each block. The disk read time above was actually for an entire block. Once the disk head is in position, one or more disk blocks can be read with little delay. With 100 records per block, the last 6 or so comparisons don't need to do any disk reads—the comparisons are all within the last disk block read.
To speed up the search further, the time to do the first 13 to 14 comparisons (which each required a disk access) must be reduced.
===An index speeds the search===
A B-tree [[Database index|index]] can be used to improve performance. A B-tree index creates a multi-level tree structure that breaks a database down into fixed-size blocks or pages. Each level of this tree can be used to link those pages via an address location, allowing one page (known as a node, or internal page) to refer to another with leaf pages at the lowest level. One page is typically the starting point of the tree, or the "root". This is where the search for a particular key would begin, traversing a path that terminates in a leaf. Most pages in this structure will be leaf pages which refer to specific table rows.
Because each node (or internal page) can have more than two children, a B-tree index will usually have a shorter height (the distance from the root to the farthest leaf) than a Binary Search Tree. In the example above, initial disk reads narrowed the search range by a factor of two. That can be improved by creating an auxiliary index that contains the first record in each disk block (sometimes called a [[Database index#Sparse index|sparse index]]). This auxiliary index would be 1% of the size of the original database, but it can be searched quickly. Finding an entry in the auxiliary index would tell us which block to search in the main database; after searching the auxiliary index, we would have to search only that one block of the main database—at a cost of one more disk read.
In the above example the index would hold 10,000 entries and would take at most 14 comparisons to return a result. Like the main database, the last six or so comparisons in the auxiliary index would be on the same disk block. The index could be searched in about eight disk reads, and the desired record could be accessed in 9 disk reads.
Creating an auxiliary index can be repeated to make an auxiliary index to the auxiliary index. That would make an aux-aux index that would need only 100 entries and would fit in one disk block.
Instead of reading 14 disk blocks to find the desired record, we only need to read 3 blocks. This blocking is the core idea behind the creation of the B-tree, where the disk blocks fill-out a hierarchy of levels to make up the index. Reading and searching the first (and only) block of the aux-aux index which is the root of the tree identifies the relevant block in aux-index in the level below. Reading and searching that aux-index block identifies the relevant block to read, until the final level, known as the leaf level, identifies a record in the main database. Instead of 150 milliseconds, we need only 30 milliseconds to get the record.
The auxiliary indices have turned the search problem from a binary search requiring roughly {{math|log<sub>2</sub> ''N''}} disk reads to one requiring only {{math|log<sub>''b''</sub> ''N''}} disk reads where {{mvar|b}} is the blocking factor (the number of entries per block: {{math|1=''b'' = 100}} entries per block in our example; {{math|1=log<sub>100</sub> 1,000,000 = 3}} reads).
In practice, if the main database is being frequently searched, the aux-aux index and much of the aux index may reside in a [[page cache|disk cache]], so they would not incur a disk read. The B-tree remains the standard index implementation in almost all [[relational database]]s, and many nonrelational databases use them too.<ref name="kleppmann_2017">{{cite book| last=Kleppmann| first=Martin| date=2017| title=Designing Data-Intensive Applications| place=[[Sebastopol, California]]| publisher=[[O'Reilly Media]]| pages=80| isbn=978-1-449-37332-0| url=https://www.academia.edu/41298363}}</ref>
===Insertions and deletions===
If the [[database]] does not change, then compiling the index is simple to do, and the index need never be changed. If there are changes, managing the database and its index require additional computation.
Deleting records from a database is relatively easy. The index can stay the same, and the record can just be marked as deleted. The database remains in sorted order. If there are a large number of [[lazy deletion]]s, then searching and storage become less efficient.<ref>
Jan Jannink.
"Implementing Deletion in B+-Trees".
Section [https://www.alexdelis.eu/M149/B+deletion.pdf "4 Lazy Deletion"].
</ref>
Insertions can be very slow in a sorted sequential file because room for the inserted record must be made. Inserting a record before the first record requires shifting all of the records down one. Such an operation is just too expensive to be practical. One solution is to leave some spaces. Instead of densely packing all the records in a block, the block can have some free space to allow for subsequent insertions. Those spaces would be marked as if they were "deleted" records.
Both insertions and deletions are fast as long as space is available on a block. If an insertion won't fit on the block, then some free space on some nearby block must be found and the auxiliary indices adjusted. The best case is that enough space is available nearby so that the amount of block reorganization can be minimized. Alternatively, some out-of-sequence disk blocks may be used.<ref name="kleppmann_2017" />
===Advantages of B-tree usage for databases===
The B-tree uses all of the ideas described above. In particular, a B-tree:
* keeps keys in sorted order for sequential traversing
* uses a hierarchical index to minimize the number of disk reads
* uses partially full blocks to speed up insertions and deletions
* keeps the index balanced with a recursive algorithm
In addition, a B-tree minimizes waste by making sure the interior nodes are at least half full. A B-tree can handle an arbitrary number of insertions and deletions.<ref name="kleppmann_2017" />
==Best case and worst case heights==
Let {{nowrap|''h'' ≥ –1}} be the height of the classic B-tree (see {{Section link|Tree (data structure)|Terminology}} for the tree height definition). Let {{nowrap|''n'' ≥ 0}} be the number of entries in the tree. Let ''m'' be the maximum number of children a node can have. Each node can have at most {{nowrap|''m''−1}} keys.
It can be shown (by induction for example) that a B-tree of height ''h'' with all its nodes completely filled has {{nowrap|1=''n'' = ''m''<sup>''h''+1</sup>–1}} entries. Hence, the best case height (i.e. the minimum height) of a B-tree is:
: <math>h_{\mathrm{min}} = \lceil \log_{m} (n+1) \rceil -1</math>
Let <math>d</math> be the minimum number of children an internal (non-root) node must have. For an ordinary B-tree, <math> d = \left\lceil m/2 \right\rceil. </math>
Comer (1979) and Cormen et al. (2001) give the worst case height (the maximum height) of a B-tree as<ref>{{harvnb|Comer|1979|p=127}}; {{harvnb|Cormen|Leiserson|Rivest|Stein|2001|pp=439–440}}</ref>
: <math>h_{\mathrm{max}} = \left\lfloor \log_{d}\frac{n+1}{2} \right\rfloor .</math>
==Algorithms==
{{confusing|reason=the discussion below uses "element", "value", "key", "separator", and "separation value" to mean essentially the same thing. The terms are not clearly defined. There are some subtle issues at the root and leaves|date=February 2012}}
===Search===
Searching is similar to searching a binary search tree. Starting at the root, the tree is recursively traversed from top to bottom. At each level, the search reduces its field of view to the child pointer (subtree) whose range includes the search value. A subtree's range is defined by the values, or keys, contained in its parent node. These limiting values are also known as separation values.
[[Binary search algorithm|Binary search]] is typically (but not necessarily) used within nodes to find the separation values and child tree of interest.
===Insertion===
[[Image:B tree insertion example.png|thumb|A B-tree insertion example with each iteration. The nodes of this B-tree have at most 3 children (Knuth order 3).]]
All insertions start at a leaf node. To insert a new element, search the tree to find the leaf node where the new element should be added. Insert the new element into that node with the following steps:
# If the node contains fewer than the maximum allowed number of elements, then there is room for the new element. Insert the new element in the node, keeping the node's elements ordered.
# Otherwise the node is full, evenly split it into two nodes so:
## A single median is chosen from among the leaf's elements and the new element that is being inserted.
## Values less than the median are put in the new left node and values greater than the median are put in the new right node, with the median acting as a separation value.
## The separation value is inserted in the node's parent, which may cause it to be split, and so on. If the node has no parent (i.e., the node was the root), create a new root above this node (increasing the height of the tree).
If the splitting goes all the way up to the root, it creates a new root with a single separator value and two children, which is why the lower bound on the size of internal nodes does not apply to the root. The maximum number of elements per node is ''U''−1. When a node is split, one element moves to the parent, but one element is added. So, it must be possible to divide the maximum number ''U''−1 of elements into two legal nodes. If this number is odd, then ''U''=2''L'' and one of the new nodes contains (''U''−2)/2 = ''L''−1 elements, and hence is a legal node, and the other contains one more element, and hence it is legal too. If ''U''−1 is even, then ''U''=2''L''−1, so there are 2''L''−2 elements in the node. Half of this number is ''L''−1, which is the minimum number of elements allowed per node.
An alternative algorithm supports a single pass down the tree from the root to the node where the insertion will take place, splitting any full nodes encountered on the way pre-emptively. This prevents the need to recall the parent nodes into memory, which may be expensive if the nodes are on secondary storage. However, to use this algorithm, we must be able to send one element to the parent and split the remaining ''U''−2 elements into two legal nodes, without adding a new element. This requires ''U'' = 2''L'' rather than ''U'' = 2''L''−1, which accounts for why some{{which|date=September 2019}} textbooks impose this requirement in defining B-trees.
===Deletion===
There are two popular strategies for deletion from a B-tree.
# Locate and delete the item, then restructure the tree to retain its invariants, '''OR'''
# Do a single pass down the tree, but before entering (visiting) a node, restructure the tree so that once the key to be deleted is encountered, it can be deleted without triggering the need for any further restructuring
The algorithm below uses the former strategy.
There are two special cases to consider when deleting an element:
# The element in an internal node is a separator for its child nodes
# Deleting an element may put its node under the minimum number of elements and children
The procedures for these cases are in order below.
====Deletion from a leaf node====
# Search for the value to delete.
# If the value is in a leaf node, simply delete it from the node.
# If underflow happens, rebalance the tree as described in section "Rebalancing after deletion" below.
====Deletion from an internal node====
Each element in an internal node acts as a separation value for two subtrees, therefore we need to find a replacement for separation. Note that the largest element in the left subtree is still less than the separator. Likewise, the smallest element in the right subtree is still greater than the separator. Both of those elements are in leaf nodes, and either one can be the new separator for the two subtrees. Algorithmically described below:
# Choose a new separator (either the largest element in the left subtree or the smallest element in the right subtree), remove it from the leaf node it is in, and replace the element to be deleted with the new separator.
# The previous step deleted an element (the new separator) from a leaf node. If that leaf node is now deficient (has fewer than the required number of nodes), then rebalance the tree starting from the leaf node.
====Rebalancing after deletion====
Rebalancing starts from a leaf and proceeds toward the root until the tree is balanced. If deleting an element from a node has brought it under the minimum size, then some elements must be redistributed to bring all nodes up to the minimum. Usually, the redistribution involves moving an element from a sibling node that has more than the minimum number of nodes. That redistribution operation is called a '''rotation'''. If no sibling can spare an element, then the deficient node must be '''merged''' with a sibling. The merge causes the parent to lose a separator element, so the parent may become deficient and need rebalancing. The merging and rebalancing may continue all the way to the root. Since the minimum element count doesn't apply to the root, making the root be the only deficient node is not a problem. The algorithm to rebalance the tree is as follows:
* If the deficient node's right sibling exists and has more than the minimum number of elements, then rotate left
*# Copy the separator from the parent to the end of the deficient node (the separator moves down; the deficient node now has the minimum number of elements)
*# Replace the separator in the parent with the first element of the right sibling (right sibling loses one node but still has at least the minimum number of elements)
*# The tree is now balanced
* Otherwise, if the deficient node's left sibling exists and has more than the minimum number of elements, then rotate right
*# Copy the separator from the parent to the start of the deficient node (the separator moves down; deficient node now has the minimum number of elements)
*# Replace the separator in the parent with the last element of the left sibling (left sibling loses one node but still has at least the minimum number of elements)
*# The tree is now balanced
* Otherwise, if both immediate siblings have only the minimum number of elements, then merge with a sibling sandwiching their separator taken off from their parent
*# Copy the separator to the end of the left node (the left node may be the deficient node or it may be the sibling with the minimum number of elements)
*# Move all elements from the right node to the left node (the left node now has the maximum number of elements, and the right node – empty)
*# Remove the separator from the parent along with its empty right child (the parent loses an element)
*#* If the parent is the root and now has no elements, then free it and make the merged node the new root (tree becomes shallower)
*#* Otherwise, if the parent has fewer than the required number of elements, then rebalance the parent<ref>{{cite web |url=https://www.cs.rhodes.edu/~kirlinp/courses/db/f16/handouts/btrees-deletion.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.cs.rhodes.edu/~kirlinp/courses/db/f16/handouts/btrees-deletion.pdf |archive-date=2022-10-09 |url-status=live |title=Deletion in a B-tree |website=cs.rhodes.edu |access-date=24 May 2022}}</ref>
:<small>'''Note''': The rebalancing operations are different for B+ trees (e.g., rotation is different because parent has copy of the key) and B<sup>*</sup>-tree (e.g., three siblings are merged into two siblings).</small>
===Sequential access===
While freshly loaded databases tend to have good sequential behaviour, this behaviour becomes increasingly difficult to maintain as a database grows, resulting in more random I/O and performance challenges.<ref>{{cite web |url=http://www.cs.sunysb.edu/~bender/pub/cache-oblivious-btree.ps |title=Cache Oblivious B-trees |publisher=State University of New York (SUNY) at Stony Brook |access-date=2011-01-17}}</ref>
===Initial construction===
{{Unreferenced section|date=April 2018}}
A common special case is adding a large amount of ''pre-sorted'' data into an initially empty B-tree. While it is quite possible to simply perform a series of successive inserts, inserting sorted data results in a tree composed almost entirely of half-full nodes. Instead, a special "bulk loading" [[algorithm]] can be used to produce a more efficient tree with a higher branching factor.
When the input is sorted, all insertions are at the rightmost edge of the tree, and in particular any time a node is split, we are guaranteed that no more insertions will take place in the left half. When bulk loading, we take advantage of this, and instead of splitting overfull nodes evenly, split them as ''unevenly'' as possible: leave the left node completely full and create a right node with zero keys and one child (in violation of the usual B-tree rules).
At the end of bulk loading, the tree is composed almost entirely of completely full nodes; only the rightmost node on each level may be less than full. Because those nodes may also be less than ''half'' full, to re-establish the normal B-tree rules, combine such nodes with their (guaranteed full) left siblings and divide the keys to produce two nodes at least half full. The only node which lacks a full left sibling is the root, which is permitted to be less than half full.
==In filesystems==
In addition to its use in databases, the B-tree (or {{section link||Variants}}) is also used in filesystems to allow quick random access to an arbitrary block in a particular file. The basic problem is turning the file block <math>i</math> address into a disk block address.
Some operating systems require the user to allocate the maximum size of the file when the file is created. The file can then be allocated as contiguous disk blocks. In that case, to convert the file block address <math>i</math> into a disk block address, the operating system simply adds the file block address <math>i</math> to the address of the first disk block constituting the file. The scheme is simple, but the file cannot exceed its created size.
Other operating systems allow a file to grow. The resulting disk blocks may not be contiguous, so mapping logical blocks to physical blocks is more involved.
[[MS-DOS]], for example, used a simple [[File Allocation Table]] (FAT). The FAT has an entry for each disk block,<ref group="note">For FAT, what is called a "disk block" here is what the FAT documentation calls a "cluster", which is a fixed-size group of one or more contiguous whole physical disk [[Cylinder-head-sector|sectors]]. For the purposes of this discussion, a cluster has no significant difference from a physical sector.</ref> and that entry identifies whether its block is used by a file and if so, which block (if any) is the next disk block of the same file. So, the allocation of each file is represented as a [[linked list]] in the table. In order to find the disk address of file block <math>i</math>, the operating system (or disk utility) must sequentially follow the file's linked list in the FAT. Worse, to find a free disk block, it must sequentially scan the FAT. For MS-DOS, that was not a huge penalty because the disks and files were small and the FAT had few entries and relatively short file chains. In the [[FAT12]] filesystem (used on floppy disks and early hard disks), there were no more than 4,080 <ref group="note">Two of these were reserved for special purposes, so only 4078 could actually represent disk blocks (clusters).</ref> entries, and the FAT would usually be resident in memory. As disks got bigger, the FAT architecture began to confront penalties. On a large disk using FAT, it may be necessary to perform disk reads to learn the disk location of a file block to be read or written.
[[TOPS-20]] (and possibly [[TENEX (operating system)|TENEX]]) used a 0 to 2 level tree that has similarities to a B-tree{{Citation needed|date=October 2009}}. A disk block was 512 36-bit words. If the file fit in a 512 (2<sup>9</sup>) word block, then the file directory would point to that physical disk block. If the file fit in 2<sup>18</sup> words, then the directory would point to an aux index; the 512 words of that index would either be NULL (the block isn't allocated) or point to the physical address of the block. If the file fit in 2<sup>27</sup> words, then the directory would point to a block holding an aux-aux index; each entry would either be NULL or point to an aux index. Consequently, the physical disk block for a 2<sup>27</sup> word file could be located in two disk reads and read on the third.
Apple's filesystem [[HFS+]] and [[APFS]], Microsoft's [[NTFS]],<ref name=insidewin2kntfs>{{cite web|url=http://msdn2.microsoft.com/en-us/library/ms995846.aspx|title=Inside Win2K NTFS, Part 1|author=Mark Russinovich|date=30 June 2006|author-link=Mark Russinovich|publisher=[[MSDN|Microsoft Developer Network]]|access-date=2008-04-18|archive-url=https://web.archive.org/web/20080413181940/http://msdn2.microsoft.com/en-us/library/ms995846.aspx|archive-date=13 April 2008<!--DASHBot-->|url-status=live}}</ref> AIX (jfs2) and some [[Linux]] filesystems, such as [[Bcachefs]], [[Btrfs]] and [[ext4]], use B-trees.
B<sup>*</sup>-trees are used in the [[Hierarchical File System (Apple)|HFS]] and [[Reiser4]] [[file system]]s.
[[DragonFly BSD]]'s [[HAMMER (file system)|HAMMER]] file system uses a modified B+-tree.<ref>{{cite web|url=https://www.dragonflybsd.org/hammer/hammer.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.dragonflybsd.org/hammer/hammer.pdf |archive-date=2022-10-09 |url-status=live|date=2008-06-21|author=Matthew Dillon|title=The HAMMER Filesystem}}</ref>
==Performance==
{{Unreferenced section|date=May 2020}}
A B-tree grows slower with growing data amount, than the linearity of a linked list. Compared to a [[skip list]], both structures have the same performance, but the B-tree scales better for growing ''n''. A [[T-tree]], for [[main memory database]] systems, is similar but more compact.
==Variations==
===Access concurrency===
Lehman and Yao<ref>{{cite journal|title=Efficient locking for concurrent operations on B-trees |year=1981 |doi=10.1145/319628.319663|last1=Lehman |first1=Philip L. |last2=Yao |first2=s. Bing |journal=ACM Transactions on Database Systems |volume=6 |issue=4 |pages=650–670 |s2cid=10756181 |doi-access=free}}</ref> showed that all the read locks could be avoided (and thus concurrent access greatly improved) by linking the tree blocks at each level together with a "next" pointer. This results in a tree structure where both insertion and search operations descend from the root to the leaf. Write locks are only required as a tree block is modified. This maximizes access concurrency by multiple users, an important consideration for databases and/or other B-tree-based [[ISAM]] storage methods. The cost associated with this improvement is that empty pages cannot be removed from the btree during normal operations. (However, see <ref>{{Cite web |last=Wang |first=Paul |date=1 February 1991 |title=An In-Depth Analysis of Concurrent B-tree Algorithms |url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf |url-status=dead |archive-url=https://web.archive.org/web/20110604175423/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf |archive-date=4 June 2011 |access-date=21 October 2022 |website=dtic.mil}}</ref> for various strategies to implement node merging, and source code at.<ref>{{cite web|url=https://github.com/malbrain/Btree-source-code|title=Downloads - high-concurrency-btree - High Concurrency B-Tree code in C - GitHub Project Hosting |website=[[GitHub]] |access-date=2014-01-27}}</ref>)
United States Patent 5283894, granted in 1994, appears to show a way to use a 'Meta Access Method' <ref>{{cite web|url=http://www.freepatentsonline.com/5283894.html|title=Lockless concurrent B-tree index meta access method for cached nodes}}</ref> to allow concurrent B+ tree access and modification without locks. The technique accesses the tree 'upwards' for both searches and updates by means of additional in-memory indexes that point at the blocks in each level in the block cache. No reorganization for deletes is needed and there are no 'next' pointers in each block as in Lehman and Yao.
===Parallel algorithms===
Since B-trees are similar in structure to [[Red–black tree|red-black trees]], [[Red–black tree#Parallel algorithms|parallel algorithms for red-black trees]] can be applied to B-trees as well.
===Maple tree===
A Maple tree is a B-tree developed for use in the [[Linux kernel]] to reduce lock contention in virtual memory management.<ref>[https://lwn.net/Articles/845507/ Introducing maple trees (LWN.net)]</ref><ref>[https://docs.kernel.org/next/core-api/maple_tree.html Maple Tree (The Linux Kernel documentation)]</ref><ref>[https://lwn.net/Articles/905638/ Introducing the Maple Tree (LWN.net / github)]</ref>
===(a,b)-tree===
(a,b)-trees are generalizations of B-trees. B-trees require that each internal node have a minimum of <math>\lfloor K / 2 \rfloor + 1</math> children and a maximum of <math>K</math> children, for some preset value of <math>K</math>. In contrast, an (a,b)-tree allows the minimum number of children for an internal node to be set arbitrarily low. In an (a,b)-tree, each internal node has between {{mvar|a}} and {{mvar|b}} children, for some preset values of {{mvar|a}} and {{mvar|b}}.
==See also==
* [[B+ tree]]
* [[R-tree]]
* [[Red–black tree]]
* [[2–3 tree]]
* [[2–3–4 tree]]
==Notes==
{{Reflist|group=note}}
==References==
{{Reflist|30em}}
{{DADS|(a,b)-tree|abtree}}
==Sources==
* {{cite journal|last1 = Bayer|first1 = R.|author-link = Rudolf Bayer|last2 = McCreight|first2 = E.|author2-link = Edward M. McCreight|title = Organization and Maintenance of Large Ordered Indexes|journal = Acta Informatica|volume = 1|issue = 3|pages = 173–189|year = 1972|url = https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf|doi =10.1007/bf00288683| s2cid = 29859053}}.
* {{cite journal|last = Comer|first = Douglas|author-link = Douglas Comer|title = The Ubiquitous B-Tree|journal = Computing Surveys|volume = 11|issue = 2|pages = 123–137|date = June 1979|issn = 0360-0300|doi = 10.1145/356770.356776|s2cid = 101673|doi-access = free}}.
* {{cite book|last1 = Cormen|first1 = Thomas|author-link = Thomas H. Cormen|last2 = Leiserson|first2 = Charles|author2-link = Charles E. Leiserson|last3 = Rivest|first3 = Ronald|author3-link = Ronald L. Rivest|last4 = Stein|first4 = Clifford|author4-link = Clifford Stein|title = [[Introduction to Algorithms]]|publisher = MIT Press and McGraw-Hill|year = 2001|edition = Second|pages = 434–454|isbn = 0-262-03293-7}} Chapter 18: B-Trees.
* {{cite book|last1 =Folk|first1 =Michael J.|last2 =Zoellick|first2 =Bill|title =File Structures|publisher =Addison-Wesley|year =1992|edition =2nd|url =https://archive.org/details/filestructures00folk|isbn =0-201-55713-4|url-access =registration}}.
* {{cite book|last = Knuth|first = Donald|author-link = Donald Knuth|series = [[The Art of Computer Programming]]|title = Sorting and Searching|publisher = Addison-Wesley|year = 1998|volume = 3|edition = Second|isbn = 0-201-89685-0}} Section 6.2.4: Multiway Trees, pp.&nbsp;481–491. Also, pp.&nbsp;476–477 of section 6.2.3 (Balanced Trees) discusses 2–3 trees.
===Original papers===
* {{Citation|last1 = Bayer|first1 = Rudolf|author-link = Rudolf Bayer|last2 = McCreight|first2 = E.|author2-link = Edward M. McCreight|title = Organization and Maintenance of Large Ordered Indices|publisher = Boeing Scientific Research Laboratories|volume = Mathematical and Information Sciences Report No. 20|date = July 1970}}.
* {{cite conference|last = Bayer|first = Rudolf|author-link = Rudolf Bayer|title = Binary B-Trees for Virtual Memory|book-title = Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control|year = 1971|place = San Diego, California}}.
==External links==
{{Commons category|B-Trees}}
*[https://www.youtube.com/watch?v=I22wEC1tTGo B-tree lecture] by David Scot Taylor, SJSU
*[https://ysangkok.github.io/js-clrs-btree/btree.html B-Tree visualisation] (click "init")
*[https://www.cs.usfca.edu/~galles/visualization/BTree.html Animated B-Tree visualization]
*[http://www.scholarpedia.org/article/B-tree_and_UB-tree B-tree and UB-tree on Scholarpedia] Curator: Dr Rudolf Bayer
*[http://www.bluerwhite.org/btree B-Trees: Balanced Tree Data Structures] {{Webarchive|url=https://web.archive.org/web/20100305211920/http://www.bluerwhite.org/btree/ |date=2010-03-05 }}
*[https://xlinux.nist.gov/dads/HTML/btree.html NIST's Dictionary of Algorithms and Data Structures: B-tree]
*[http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html B-Tree Tutorial]
*[https://web.archive.org/web/20110708080729/http://boilerbay.com/infinitydb/TheDesignOfTheInfinityDatabaseEngine.htm The InfinityDB BTree implementation]
*[http://supertech.csail.mit.edu/cacheObliviousBTree.html Cache Oblivious B(+)-trees]
*[https://xlinux.nist.gov/dads/HTML/bstartree.html Dictionary of Algorithms and Data Structures entry for B*-tree]
*[http://opendatastructures.org/versions/edition-0.1g/ods-python/14_2_B_Trees.html Open Data Structures - Section 14.2 - B-Trees], [[Pat Morin]]
*[http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html Counted B-Trees]
*[http://sop.codeplex.com B-Tree .Net, a modern, virtualized RAM & Disk implementation]
'''Bulk loading'''
*{{cite thesis |last=Shetty |first=Soumya B. |title=A user configurable implementation of B-trees |date=2010 |url=https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=2336&context=etd |publisher=Iowa State University}}
*{{cite web |first=Semih |last=Kaldırım |title=File Organization, ISAM, B+ Tree and Bulk Loading |date= 28 April 2015 |publisher=[[Bilkent University]] |location=Ankara, Turkey |pages=4–6 |url=http://www.cs.bilkent.edu.tr/~canf/CS281Spring15LectureNotesFeb13/Week13.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.bilkent.edu.tr/~canf/CS281Spring15LectureNotesFeb13/Week13.pdf |archive-date=2022-10-09 |url-status=live}}
*{{cite web |title=ECS 165B: Database System Implementation: Lecture 6 |date=9 April 2010 |page=23 |url=http://web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://web.cs.ucdavis.edu/~green/courses/ecs165b-s10/Lecture6.pdf |archive-date=2022-10-09 |url-status=live |publisher=[[University of California, Davis]]}}
* {{cite web| url=https://docs.microsoft.com/en-us/sql/t-sql/statements/bulk-insert-transact-sql?view=sql-server-2017| title=BULK INSERT (Transact-SQL) in SQL Server 2017| publisher=Microsoft Docs| date=6 September 2018}}
{{CS-Trees}}
{{Data structures}}
{{DEFAULTSORT:B-Tree}}
[[Category:B-tree| ]]
[[Category:Computer-related introductions in 1971]]
[[Category:Database index techniques]]