B-tree - Knowledge (XXG)

3827:) used a 0 to 2 level tree that has similarities to a B-tree. A disk block was 512 36-bit words. If the file fit in a 512 (2) word block, then the file directory would point to that physical disk block. If the file fit in 2 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 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 word file could be located in two disk reads and read on the third. 2621:

splitting operation as long as they can. 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. 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

2816:. 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. 3896: 3614: 2617:, 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. 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. 3265: 2713: 2851:

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.

2840:). 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. 539: 3812:, 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 2832:

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.

2575:

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

451:

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

3528:

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

3519:

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

3323:

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

3686:

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

2928:

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

525:

is also inconsistent. Bayer and 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. There are many possible implementation choices. In some designs, the leaves may hold the entire data record; in other

3985:

Lehman and Yao 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

2805:

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

2683:

lowest keys stay in the current node, the next (middle) key is inserted in the parent and the rest go to the right sibling. (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. When both the sibling nodes are full,

3994:

United States Patent 5283894, granted in 1994, appears to show a way to use a 'Meta Access Method' 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

3816:

filesystem (used on floppy disks and early hard disks), there were no more than 4,080 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

2850:

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

2620:

The B tree balances more neighboring internal nodes to keep the internal nodes more densely packed. This variant ensures non-root nodes are at least 2/3 full instead of 1/2. As the most costly part of operation of inserting the node in B-tree is splitting the node, B-trees are created to postpone

2843:

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

3500:

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

2932:

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

2835:

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

2831:

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

3418:

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

513:

of B-tree as the minimum number of keys in a non-root node. Folk and Zoellick 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

2684:

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. If the parent is full, then spill/split operation propagates towards the root node. Deleting nodes is somewhat more complex than inserting however.

3698:

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.

2588:, 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 2604:

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

3370:

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

2495:-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 3788:(FAT). The FAT has an entry for each disk block, 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 261:, 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 3678:

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"

2515:-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 3249: 3280:. In particular, 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. 470:

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

3990:

storage methods. The cost associated with this improvement is that empty pages cannot be removed from the btree during normal operations. (However, see for various strategies to implement node merging, and source code at.)

3363:

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

529:

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.

3734:

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

3505:

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

3092: 3599:

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.

3457:

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

3509:

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

3346:

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:

2354:

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

2921:

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

2564:

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.

3694:

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

2847:

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.

2572:

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.

3162: 2632:

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

2073: 2918:

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.

498:

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.

2592:

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.

3589:: The rebalancing operations are different for B+ trees (e.g., rotation is different because parent has copy of the key) and B-tree (e.g., three siblings are merged into two siblings). 3351:

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.

2929:

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.

2801:

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

2031: 1963: 495:, 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. 2140: 3986:

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

4472: 354:

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:

3360:

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.

4351: 4071:

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

407:) 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 1457: 1394: 1181: 1089: 997: 788: 762: 2958:

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.

1796: 1704: 1645: 1553: 1490: 1299: 1240: 1148: 1056: 964: 905: 645: 613: 6110: 4717: 3539:

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)

1763: 1731: 1672: 1520: 1421: 1358: 1326: 1267: 1208: 1116: 1024: 932: 674: 2473: 2332: 3561:

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

2559: 2398: 2269: 2100: 1923: 3553:

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)

2441: 2303: 2223: 729: 3810: 3773: 3753: 3729: 3115: 2533: 2513: 2493: 2418: 2372: 2352: 2243: 2200: 2161: 1984: 1893: 1858: 694: 4300:

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.

3778:

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.

3172: 6071: 4571: 5161: 3536:

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)

2698:

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.

2809:

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.

3550:

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)

5747: 5096: 3995:

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.

3564:

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)

3501:

separator. Both of those elements are in leaf nodes, and either one can be the new separator for the two subtrees. Algorithmically described below:

3711:) 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 3339: 3691:

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).

5183: 458:

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

6041: 5472: 4515: 4397: 2374:

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

5679: 3375:−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 2731: 2723: 3567:

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)

302:

have been suggested. McCreight has said that "the more you think about what the B in B-trees means, the better you understand B-trees".

3019: 6115: 5223: 5194: 5980: 4997: 4970: 4946: 4629: 4335: 3943: 3661: 3305: 2749: 226: 2819:

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.

3862: 3775:

to the address of the first disk block constituting the file. The scheme is simple, but the file cannot exceed its created size.

5339: 5770: 5179: 4989: 5004:

Section 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2–3 trees.

3573:

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)

5775: 3921: 3639: 3419:

secondary storage. However, to use this algorithm, we must be able to send one element to the parent and split the remaining

2806:

and the average reading seek time is 8.5 milliseconds. For simplicity, assume reading from disk takes about 10 milliseconds.

423:

children. Thus, the number of elements is always 1 less than the number of child pointers (the number of elements is between

2898:

In practice, if the main database is being frequently searched, the aux-aux index and much of the aux index may reside in a

4658: 3547:

Otherwise, if the deficient node's left sibling exists and has more than the minimum number of elements, then rotate right

5740: 2767:

Sorting and searching algorithms can be characterized by the number of comparison operations that must be performed using

526:

designs, the leaves may only hold pointers to the data record. Those choices are not fundamental to the idea of a B-tree.

4728: 5854: 5837: 4211: 2790:

comparisons. If the table had 1,000,000 records, then a specific record could be located with at most 20 comparisons:

3906: 3624: 3283: 3120: 6053: 5820: 5815: 5304: 5111: 4937: 583:: Maximum number of potential search keys for each node in a B-tree. (this value is constant over the entire tree). 3925: 3910: 3643: 3628: 2035: 5810: 5689: 4560: 4116:

Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70

3342:

A B-tree insertion example with each iteration. The nodes of this B-tree have at most 3 children (Knuth order 3).

3533:

If the deficient node's right sibling exists and has more than the minimum number of elements, then rotate left

5849: 5844: 5803: 5733: 5245: 5150: 3824: 3395:−1 elements, and hence is a legal node, and the other contains one more element, and hence it is legal too. If 3330:

is typically (but not necessarily) used within nodes to find the separation values and child tree of interest.

5139: 5077: 4084:

Two of these were reserved for special purposes, so only 4078 could actually represent disk blocks (clusters).

2836:

improved by creating an auxiliary index that contains the first record in each disk block (sometimes called a

6084: 6061: 3917: 3635: 3327: 222: 49: 1990: 479:/2-1 if they are not the root) and pointers (one for each key) to nodes carrying the data objects / chunks. 6066: 5866: 5216: 4503: 2902:, so they would not incur a disk read. The B-tree remains the standard index implementation in almost all 3520:

a sibling node that has more than the minimum number of nodes. That redistribution operation is called a

3275: 2643:

keys, then keys are redistributed between the two sibling nodes as evenly as possible. For this purpose,

1934: 5992: 5947: 5909: 5383: 5232: 5026:, vol. Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories 3785: 2974: 404: 54: 2420:

keys plus one more key brought down from the neighbor's parent. The result is an entirely full node of

2111: 4075:. For the purposes of this discussion, a cluster has no significant difference from a physical sector. 5932: 5373: 5328: 5120: 4924: 4459: 4072: 3969: 3879: 3166:

Comer (1979) and Cormen et al. (2001) give the worst case height (the maximum height) of a B-tree as

2695: 2589: 230: 5172: 3570:

Remove the separator from the parent along with its empty right child (the parent loses an element)

3491:

If underflow happens, rebalance the tree as described in section "Rebalancing after deletion" below.

3357:

A single median is chosen from among the leaf's elements and the new element that is being inserted.

5487: 5263: 5019: 4833: 4052: 3956:

A B-tree grows slower with growing data amount, than the linearity of a linked list. Compared to a

2903: 462:−1 elements in the entire tree, the root will be the only node in the tree with no children at all. 254: 210: 76: 5975: 5343: 4042: 4008: 4004: 3576:

Otherwise, if the parent has fewer than the required number of elements, then rebalance the parent

5960: 5825: 5785: 5654: 5613: 5439: 5429: 5308: 5157: 4907: 4860: 4837: 4754:"Downloads - high-concurrency-btree - High Concurrency B-Tree code in C - GitHub Project Hosting" 4698: 4436: 4345: 4127: 4108: 3117:

be the minimum number of children an internal (non-root) node must have. For an ordinary B-tree,

2179:

In order to maintain the predefined range of child nodes, internal nodes may be joined or split.

218: 4596: 213:

that maintains sorted data and allows searches, sequential access, insertions, and deletions in

5091: 3324:

keys, contained in its parent node. These limiting values are also known as separation values.

5894: 5793: 5548: 5249: 5209: 4993: 4966: 4942: 4899: 4511: 4507: 4393: 4331: 2933:

reorganization can be minimized. Alternatively, some out-of-sequence disk blocks may be used.

2577: 27:

A self-balancing, tree-based data structure, that allows read/write access in logarithmic time

1429: 1366: 1153: 1061: 969: 767: 734: 5917: 5639: 5063: 4928: 4920: 4889: 4852: 4688: 4617: 4426: 4414: 4119: 2854:

The auxiliary indices have turned the search problem from a binary search requiring roughly

2276: 1771: 1679: 1620: 1528: 1465: 1274: 1215: 1123: 1031: 939: 880: 620: 588: 267: 214: 202: 170: 1741: 1709: 1650: 1498: 1399: 1336: 1304: 1245: 1186: 1094: 1002: 910: 652: 6105: 5937: 5879: 5583: 5333: 5101: 5081: 3338: 2449: 2308: 518:

to be the maximum number of children (which is one more than the maximum number of keys).

87: 5068: 4621: 2538: 2377: 2248: 2079: 1902: 559:

As with other trees, B-trees can be represented as a collection of three types of nodes:

4803: 3244:{\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .} 2423: 2285: 2205: 793:

All leaf nodes have the same number of ancestors (i.e., they are all at the same depth).

6029: 6007: 5832: 5756: 5536: 5531: 5414: 5348: 4932: 3795: 3758: 3738: 3714: 3439:−1, which accounts for why some textbooks impose this requirement in defining B-trees. 3100: 2837: 2828: 2768: 2561:

keys, in which case the two siblings and parent are merged, reducing the depth by one.

2518: 2498: 2478: 2403: 2357: 2337: 2305:

keys, then adding a key to that node can be accomplished by splitting the hypothetical

2228: 2185: 2146: 1969: 1878: 1843: 707: 679: 91: 5057: 4431: 3960:, both structures have the same performance, but the B-tree scales better for growing 3472:

Deleting an element may put its node under the minimum number of elements and children

2446:

A B-tree is kept balanced after insertion by splitting a would-be overfilled node, of

6099: 6002: 5899: 5884: 5684: 5664: 5507: 5396: 5323: 4873: 4440: 3875: 2922: 2812:

The search time is reduced because individual records are grouped together in a disk

2772: 2585: 229:, the B-tree is well suited for storage systems that read and write relatively large 5258: 4864: 4702: 4131: 4047: 5644: 5608: 5424: 5419: 5401: 5313: 5106: 5032: 5015: 4981: 4959: 4829: 4020: 3755:

into a disk block address, the operating system simply adds the file block address

2650:

keys from the current node, the new key inserted, one key from the parent node and

311: 250: 72: 4911: 5037:

Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control

4651: 4284:

avoided the issue by saying an index element is a (physically adjacent) pair of (

2279:

of the tree. The factor of 2 will guarantee that nodes can be split or combined.

443:−1; therefore each internal node is at least half full. The relationship between 5997: 5922: 5694: 5659: 5649: 5563: 5497: 5492: 5482: 5391: 5240: 4779: 4753: 3895: 3869: 3789: 3613: 3451:

Locate and delete the item, then restructure the tree to retain its invariants,

3287: 238: 31: 5086: 4531: 4330:(6th ed.). Upper Saddle River, N.J.: Pearson Education. pp. 652–660. 3013:

entries. Hence, the best case height (i.e. the minimum height) of a B-tree is:

5985: 5889: 5704: 5674: 5634: 5477: 5406: 5353: 5273: 5051: 4304:

states, "For this paper the associated information is of no further interest."

3423:−2 elements into two legal nodes, without adding a new element. This requires 2988:

be the maximum number of children a node can have. Each node can have at most

2899: 2581: 4903: 3683:

can be used to produce a more efficient tree with a higher branching factor.

5927: 5874: 5709: 5669: 5516: 5444: 5434: 5115: 4123: 3957: 3680: 2802: 2272: 4219: 2941:

The B-tree uses all of the ideas described above. In particular, a B-tree:

6024: 5598: 5288: 4894: 4877: 4693: 4676: 4032: 2688: 2614: 2606: 35: 5970: 5798: 5714: 5588: 5568: 5541: 5526: 5278: 4474:

Product Manual: Barracuda ES.2 Serial ATA, Rev. F., publication 100468393

3847: 2915: 234: 6019: 5965: 5699: 5603: 5578: 5521: 5368: 5298: 5293: 5268: 5201: 4856: 3866: 3820: 4780:"Lockless concurrent B-tree index meta access method for cached nodes" 3524:. If no sibling can spare an element, then the deficient node must be 17: 6014: 5618: 5593: 5573: 5558: 5467: 5358: 4758: 4425:(3). Institute for System Programming of the RAS (ISP RAS): 203–216. 4415:"SQLite RDBMS Extension for Data Indexing Using B-tree Modifications" 4037: 3965: 3781: 700:

In B-trees, the following properties are maintained for these nodes:

258: 4497: 4814: 4792: 3831: 2998:

It can be shown (by induction for example) that a B-tree of height

5725: 5462: 5363: 5318: 5074: 3851: 3843: 3813: 3529:

not a problem. The algorithm to rebalance the tree is as follows:

3469:

The element in an internal node is a separator for its child nodes

3465:

There are two special cases to consider when deleting an element:

3337: 538: 537: 3379:−1 of elements into two legal nodes. If this number is odd, then 3087:{\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1} 6036: 5454: 5126:

B-Tree .Net, a modern, virtualized RAM & Disk implementation

4941:(Second ed.). MIT Press and McGraw-Hill. pp. 434–454. 4625: 3987: 3855: 3839: 3835: 509:

Bayer and McCreight (1972), Comer (1979), and others define the

5729: 5205: 3488:

If the value is in a leaf node, simply delete it from the node.

3354:

Otherwise the node is full, evenly split it into two nodes so:

2951:

uses partially full blocks to speed up insertions and deletions

389:, and all values in the rightmost subtree will be greater than 5107:

Dictionary of Algorithms and Data Structures entry for B*-tree

4419:

Proceedings of the Institute for System Programming of the RAS

3889: 3792:

in the table. In order to find the disk address of file block

3607: 3415:−1, which is the minimum number of elements allowed per node. 3258: 2948:

uses a hierarchical index to minimize the number of disk reads

2706: 329:

Every node, except for the root and the leaves, has at least ⌈

4265: 4263: 4197: 3447:

There are two popular strategies for deletion from a B-tree.

506:

The literature on B-trees is not uniform in its terminology.

4164: 4162: 4160: 1426:

Points to subtree in which all search keys are greater than

1363:

Points to subtree in which all search keys are greater than

336:

The root node has at least two children unless it is a leaf.

5087:

NIST's Dictionary of Algorithms and Data Structures: B-tree

2654:

keys from the sibling node are seen as an ordered array of

274:

Bayer and McCreight never explained what, if anything, the

5125: 4547: 4530:

Jan Jannink. "Implementing Deletion in B+-Trees". Section

2880:

is the blocking factor (the number of entries per block:

1333:

Points to subtree in which all search keys are less than

797:

Each internal node in a B-tree has the following format:

265:

was first circulated in July 1970 and later published in

4677:"Efficient locking for concurrent operations on B-trees" 4118:. Boeing Scientific Research Laboratories. p. 107. 4023:

to reduce lock contention in virtual memory management.

4838:"Organization and Maintenance of Large Ordered Indexes" 4392:. Belgrade, Serbia: Akademska misao. pp. 274–275. 4109:"Organization and maintenance of large ordered indices" 368:. All values in the leftmost subtree will be less than 4718:"An In-Depth Analysis of Concurrent B-tree Algorithms" 4238: 4236: 4102: 4100: 2182:

Usually, the number of keys is chosen to vary between

710: 615:: The pointer to a child node which starts a sub-tree. 5173:"ECS 165B: Database System Implementation: Lecture 6" 5024:

Organization and Maintenance of Large Ordered Indices

3817:

disk location of a file block to be read or written.

3798: 3761: 3741: 3717: 3175: 3123: 3103: 3022: 2541: 2521: 2501: 2481: 2452: 2426: 2406: 2380: 2360: 2340: 2311: 2288: 2251: 2231: 2208: 2188: 2149: 2114: 2082: 2038: 1993: 1972: 1937: 1905: 1881: 1846: 1774: 1744: 1712: 1682: 1653: 1623: 1561:

Each leaf node in a B-tree has the following format:

1531: 1501: 1468: 1432: 1402: 1369: 1339: 1307: 1277: 1248: 1218: 1189: 1156: 1126: 1097: 1064: 1034: 1005: 972: 942: 913: 883: 770: 737: 682: 655: 623: 591: 263:

Organization and maintenance of large ordered indices

4599:. State University of New York (SUNY) at Stony Brook 3707:

In addition to its use in databases, the B-tree (or

2945:

keeps keys in sorted order for sequential traversing

2925:, then searching and storage become less efficient. 318:

is a tree which satisfies the following properties:

6052: 5946: 5908: 5865: 5784: 5763: 5627: 5506: 5453: 5382: 5239: 5151:"File Organization, ISAM, B+ Tree and Bulk Loading" 4147: 4145: 4143: 4141: 3476:The procedures for these cases are in order below. 2954:

keeps the index balanced with a recursive algorithm

1804:The node bounds are summarized in the table below: 375:, all values in the middle subtree will be between 176: 169: 150: 131: 112: 97: 86: 68: 60: 48: 43: 4958: 4019:A Maple tree is a B-tree developed for use in the 3804: 3767: 3747: 3723: 3674:A common special case is adding a large amount of 3243: 3156: 3109: 3086: 2553: 2527: 2507: 2487: 2467: 2435: 2412: 2392: 2366: 2346: 2326: 2297: 2263: 2237: 2217: 2194: 2155: 2134: 2094: 2067: 2025: 1978: 1957: 1917: 1887: 1852: 1790: 1757: 1725: 1698: 1666: 1639: 1547: 1514: 1484: 1451: 1415: 1388: 1352: 1320: 1293: 1261: 1234: 1202: 1175: 1142: 1110: 1083: 1050: 1018: 991: 958: 926: 899: 782: 756: 723: 688: 668: 639: 607: 4992:. Vol. 3 (Second ed.). Addison-Wesley. 4491: 4489: 4487: 2906:, and many nonrelational databases use them too. 3411:−2 elements in the node. Half of this number is 647:: The pointer to a record which stores the data. 5195:"BULK INSERT (Transact-SQL) in SQL Server 2017" 3157:{\displaystyle d=\left\lceil m/2\right\rceil .} 2665:keys. The array becomes split by half, so that 2584:. By maximizing the number of keys within each 4301: 4281: 4212:"Stanford Center for Professional Development" 4168: 3462:The algorithm below uses the former strategy. 676:: The search key at the zero-based node index 543: 5741: 5217: 5141:A user configurable implementation of B-trees 5112:Open Data Structures - Section 14.2 - B-Trees 5035:(1971). "Binary B-Trees for Virtual Memory". 4815:Introducing the Maple Tree (LWN.net / github) 2779:records, for example, can be done in roughly 8: 4413:Rigin A. M., Shershakov S. A. (2019-09-10). 4350:: CS1 maint: multiple names: authors list ( 4326:Navathe, Ramez Elmasri, Shamkant B. (2010). 4313: 4269: 4254: 3286:. There might be a discussion about this on 3075: 3044: 2129: 2115: 2068:{\displaystyle \equiv \lfloor K/2\rfloor +1} 2056: 2042: 2020: 1994: 1952: 1938: 4804:Maple Tree (The Linux Kernel documentation) 4191: 4189: 3924:. Unsourced material may be challenged and 3642:. Unsourced material may be challenged and 5748: 5734: 5726: 5224: 5210: 5202: 4480:. Seagate Technology LLC. 2008. p. 6. 4003:Since B-trees are similar in structure to 2984:be the number of entries in the tree. Let 2844:record could be accessed in 9 disk reads. 225:with more than two children. Unlike other 83: 4957:Folk, Michael J.; Zoellick, Bill (1992). 4893: 4692: 4430: 3944:Learn how and when to remove this message 3797: 3760: 3740: 3716: 3662:Learn how and when to remove this message 3306:Learn how and when to remove this message 3215: 3206: 3181: 3180: 3174: 3138: 3122: 3102: 3051: 3028: 3027: 3021: 3002:with all its nodes completely filled has 2973:be the height of the classic B-tree (see 2750:Learn how and when to remove this message 2540: 2520: 2500: 2480: 2451: 2425: 2405: 2379: 2359: 2339: 2310: 2287: 2250: 2230: 2207: 2187: 2148: 2121: 2113: 2081: 2048: 2037: 2012: 1992: 1971: 1944: 1936: 1904: 1880: 1845: 1782: 1773: 1749: 1743: 1738:Points to a record with a value equal to 1717: 1711: 1690: 1681: 1658: 1652: 1631: 1622: 1539: 1530: 1506: 1500: 1495:Points to a record with a value equal to 1476: 1467: 1437: 1431: 1407: 1401: 1374: 1368: 1344: 1338: 1312: 1306: 1285: 1276: 1253: 1247: 1226: 1217: 1194: 1188: 1161: 1155: 1134: 1125: 1102: 1096: 1069: 1063: 1042: 1033: 1010: 1004: 977: 971: 950: 941: 918: 912: 891: 882: 769: 742: 736: 715: 709: 681: 660: 654: 631: 622: 599: 590: 574:Note the following variable definitions: 491:times as many items as a B-tree of depth 4675:Lehman, Philip L.; Yao, s. Bing (1981). 2975:Tree (data structure) § Terminology 2937:Advantages of B-tree usage for databases 1806: 1611: 1563: 871: 799: 4383: 4381: 4379: 4377: 4375: 4373: 4096: 4064: 4009:parallel algorithms for red-black trees 6111:Computer-related introductions in 1971 5075:B-Trees: Balanced Tree Data Structures 4343: 4107:Bayer, R.; McCreight, E. (July 1970). 3972:systems, is similar but more compact. 1870:Root node when it is an internal node 731:exists in any node in a B+ tree, then 40: 4543: 4499:Designing Data-Intensive Applications 4364: 4242: 4180: 4151: 3882:file system uses a modified B+-tree. 2977:for the tree height definition). Let 2400:keys; joining the neighbor would add 2026:{\displaystyle \lceil (K+1)/2\rceil } 547: 7: 4681:ACM Transactions on Database Systems 3922:adding citations to reliable sources 3640:adding citations to reliable sources 339:All leaves appear on the same level. 5197:. Microsoft Docs. 6 September 2018. 5097:The InfinityDB BTree implementation 4196:Weiner, Peter G. (30 August 2013). 4011:can be applied to B-trees as well. 3731:address into a disk block address. 3387:and one of the new nodes contains ( 2245:is the minimum number of keys, and 1958:{\displaystyle \lfloor K/2\rfloor } 5069:B-tree and UB-tree on Scholarpedia 4632:from the original on 13 April 2008 3188: 3185: 3182: 3035: 3032: 3029: 2887:entries per block in our example; 2722:tone or style may not reflect the 227:self-balancing binary search trees 25: 5149:Kaldırım, Semih (28 April 2015). 4793:Introducing maple trees (LWN.net) 2864:disk reads to one requiring only 2135:{\displaystyle \lceil K/2\rceil } 1835:Root node when it is a leaf node 314:'s definition, a B-tree of order 5189:from the original on 2022-10-09. 5167:from the original on 2022-10-09. 5144:(Thesis). Iowa State University. 4965:(2nd ed.). Addison-Wesley. 4664:from the original on 2022-10-09. 4328:Fundamentals of database systems 3894: 3612: 3263: 2962:Best case and worst case heights 2732:guide to writing better articles 2711: 873:Internal node pointer structure 5180:University of California, Davis 4990:The Art of Computer Programming 4577:from the original on 2022-10-09 3485:Search for the value to delete. 4716:Wang, Paul (1 February 1991). 4390:Algorithms and Data Structures 3496:Deletion from an internal node 3072: 3060: 2009: 1997: 403:Internal nodes (also known as 1: 5064:Animated B-Tree visualization 4650:Matthew Dillon (2008-06-21). 4432:10.15514/ispras-2019-31(3)-16 3784:, for example, used a simple 3708: 2691:and B tree features together. 2687:The B tree combines the main 2609:, the B tree and the B tree. 217:. The B-tree generalizes the 5182:. 9 April 2010. p. 23. 4302:Bayer & McCreight (1972) 4282:Bayer & McCreight (1972) 2763:Time to search a sorted file 1613:Leaf node pointer structure 6072:Directed acyclic word graph 5838:Double-ended priority queue 4626:Microsoft Developer Network 4622:"Inside Win2K NTFS, Part 1" 2694:B-trees can be turned into 6132: 5138:Shetty, Soumya B. (2010). 5102:Cache Oblivious B(+)-trees 5054:by David Scot Taylor, SJSU 4938:Introduction to Algorithms 4496:Kleppmann, Martin (2017). 4169:Bayer & McCreight 1972 3515:Rebalancing after deletion 2823:An index speeds the search 764:exists in that node where 544:Bayer & McCreight 1972 502:Differences in terminology 29: 6116:Database index techniques 6080: 4597:"Cache Oblivious B-trees" 4183:, p. 123 footnote 1. 3480:Deletion from a leaf node 2703:B-tree usage in databases 2568:Comparison to other trees 249:B-trees were invented by 82: 5804:Retrieval Data Structure 5680:Left-child right-sibling 5071:Curator: Dr Rudolf Bayer 5039:. San Diego, California. 4388:Tomašević, Milo (2008). 4314:Folk & Zoellick 1992 4270:Folk & Zoellick 1992 4255:Folk & Zoellick 1992 3861:B-trees are used in the 3556:The tree is now balanced 3542:The tree is now balanced 2910:Insertions and deletions 2282:If an internal node has 801:Internal node structure 30:Not to be confused with 6085:List of data structures 6062:Binary decision diagram 5510:data partitioning trees 5468:C-trie (compressed ADT) 4878:"The Ubiquitous B-Tree" 4652:"The HAMMER Filesystem" 4198:"4- Edward M McCreight" 4124:10.1145/1734663.1734671 2775:of a sorted table with 2726:used on Knowledge (XXG) 1452:{\displaystyle k_{i-1}} 1389:{\displaystyle k_{i-1}} 1176:{\displaystyle k_{i-1}} 1084:{\displaystyle k_{i-1}} 992:{\displaystyle k_{i-1}} 783:{\displaystyle i\geq 1} 757:{\displaystyle k_{i-1}} 567:(a.k.a. interior), and 322:Every node has at most 6067:Directed acyclic graph 4561:"Deletion in a B-tree" 4504:Sebastopol, California 4462:, retrieved 2010-01-25 3842:, AIX (jfs2) and some 3806: 3769: 3749: 3725: 3343: 3245: 3158: 3111: 3088: 2730:See Knowledge (XXG)'s 2555: 2529: 2509: 2489: 2469: 2437: 2414: 2394: 2368: 2348: 2328: 2299: 2265: 2239: 2219: 2196: 2175:Insertion and deletion 2157: 2136: 2096: 2069: 2027: 1980: 1959: 1919: 1889: 1854: 1792: 1791:{\displaystyle pr_{i}} 1759: 1727: 1700: 1699:{\displaystyle pr_{i}} 1668: 1641: 1640:{\displaystyle pr_{i}} 1549: 1548:{\displaystyle pr_{i}} 1516: 1486: 1485:{\displaystyle pt_{i}} 1453: 1417: 1390: 1354: 1322: 1295: 1294:{\displaystyle pr_{i}} 1263: 1236: 1235:{\displaystyle pr_{i}} 1204: 1177: 1144: 1143:{\displaystyle pt_{i}} 1112: 1085: 1052: 1051:{\displaystyle pt_{i}} 1020: 993: 960: 959:{\displaystyle pt_{i}} 928: 901: 900:{\displaystyle pt_{0}} 784: 758: 725: 690: 670: 641: 640:{\displaystyle pr_{i}} 609: 608:{\displaystyle pt_{i}} 551: 4986:Sorting and Searching 4895:10.1145/356770.356776 4694:10.1145/319628.319663 3846:filesystems, such as 3807: 3786:File Allocation Table 3770: 3750: 3726: 3341: 3246: 3159: 3112: 3089: 2696:order statistic trees 2556: 2535:and (transitionally) 2530: 2510: 2490: 2470: 2438: 2415: 2395: 2369: 2349: 2329: 2300: 2266: 2240: 2220: 2197: 2158: 2137: 2097: 2070: 2028: 1981: 1960: 1920: 1890: 1855: 1793: 1760: 1758:{\displaystyle k_{i}} 1728: 1726:{\displaystyle k_{i}} 1701: 1669: 1667:{\displaystyle k_{i}} 1642: 1550: 1517: 1515:{\displaystyle k_{i}} 1487: 1454: 1418: 1416:{\displaystyle k_{i}} 1391: 1355: 1353:{\displaystyle k_{0}} 1323: 1321:{\displaystyle k_{i}} 1296: 1264: 1262:{\displaystyle k_{i}} 1237: 1205: 1203:{\displaystyle k_{i}} 1178: 1145: 1113: 1111:{\displaystyle k_{i}} 1086: 1053: 1021: 1019:{\displaystyle k_{i}} 994: 961: 929: 927:{\displaystyle k_{0}} 902: 785: 759: 726: 691: 671: 669:{\displaystyle k_{i}} 642: 610: 541: 342:A non-leaf node with 55:Tree (data structure) 5933:Unrolled linked list 5690:Log-structured merge 5233:Tree data structures 5058:B-Tree visualisation 4953:Chapter 18: B-Trees. 3970:main memory database 3918:improve this section 3796: 3759: 3739: 3715: 3636:improve this section 3604:Initial construction 3276:confusing or unclear 3173: 3121: 3101: 3020: 2904:relational databases 2539: 2519: 2499: 2479: 2468:{\displaystyle 2d+1} 2450: 2424: 2404: 2378: 2358: 2338: 2327:{\displaystyle 2d+1} 2309: 2286: 2249: 2229: 2206: 2186: 2147: 2112: 2080: 2036: 1991: 1970: 1935: 1903: 1879: 1844: 1772: 1742: 1710: 1680: 1651: 1621: 1565:Leaf node structure 1529: 1499: 1466: 1430: 1400: 1367: 1337: 1305: 1275: 1246: 1216: 1187: 1154: 1124: 1095: 1062: 1032: 1003: 970: 940: 911: 881: 768: 735: 708: 680: 653: 621: 589: 534:Informal description 259:Boeing Research Labs 209:is a self-balancing 5981:Self-balancing tree 3999:Parallel algorithms 3830:Apple's filesystem 3284:clarify the article 2554:{\displaystyle d-1} 2393:{\displaystyle d-1} 2264:{\displaystyle d+1} 2095:{\displaystyle K+1} 1918:{\displaystyle K+1} 1614: 1566: 874: 802: 255:Edward M. McCreight 211:tree data structure 77:Edward M. McCreight 5961:Binary search tree 5826:Double-ended queue 5655:Fractal tree index 5250:associative arrays 5158:Bilkent University 5156:. Ankara, Turkey: 5080:2010-03-05 at the 4925:Leiserson, Charles 4857:10.1007/bf00288683 4550:, pp. 439–440 4548:Cormen et al. 2001 4200:– via Vimeo. 3981:Access concurrency 3802: 3765: 3745: 3721: 3407:−1, so there are 2 3344: 3241: 3154: 3107: 3084: 2796:(1,000,000) ⌉ = 20 2551: 2525: 2505: 2485: 2465: 2436:{\displaystyle 2d} 2433: 2410: 2390: 2364: 2344: 2334:key node into two 2324: 2298:{\displaystyle 2d} 2295: 2261: 2235: 2218:{\displaystyle 2d} 2215: 2192: 2153: 2132: 2092: 2065: 2023: 1976: 1955: 1915: 1885: 1850: 1788: 1755: 1723: 1696: 1664: 1637: 1612: 1564: 1545: 1512: 1482: 1449: 1413: 1396:and are less than 1386: 1350: 1318: 1291: 1259: 1232: 1200: 1173: 1140: 1108: 1081: 1048: 1016: 989: 956: 924: 897: 872: 800: 780: 754: 724:{\textstyle k_{i}} 721: 686: 666: 637: 605: 552: 487:+1 can hold about 483:A B-tree of depth 346:children contains 219:binary search tree 6093: 6092: 5895:Hashed array tree 5794:Associative array 5723: 5722: 4882:Computing Surveys 4532:"4 Lazy Deletion" 4517:978-1-449-37332-0 4399:978-86-7466-328-8 4216:scpd.stanford.edu 3954: 3953: 3946: 3805:{\displaystyle i} 3768:{\displaystyle i} 3748:{\displaystyle i} 3724:{\displaystyle i} 3672: 3671: 3664: 3595:Sequential access 3590: 3399:−1 is even, then 3316: 3315: 3308: 3231: 3110:{\displaystyle d} 2876:disk reads where 2760: 2759: 2752: 2724:encyclopedic tone 2578:secondary storage 2528:{\displaystyle d} 2508:{\displaystyle d} 2488:{\displaystyle d} 2413:{\displaystyle d} 2367:{\displaystyle d} 2347:{\displaystyle d} 2238:{\displaystyle d} 2195:{\displaystyle d} 2172: 2171: 2156:{\displaystyle K} 1979:{\displaystyle K} 1888:{\displaystyle K} 1853:{\displaystyle K} 1802: 1801: 1610: 1609: 1559: 1558: 870: 869: 689:{\displaystyle i} 475:-1, and at least 257:while working at 199: 198: 195: 194: 16:(Redirected from 6123: 5918:Association list 5750: 5743: 5736: 5727: 5226: 5219: 5212: 5203: 5198: 5190: 5188: 5177: 5168: 5166: 5160:. pp. 4–6. 5155: 5145: 5040: 5027: 5003: 4976: 4964: 4952: 4915: 4897: 4868: 4845:Acta Informatica 4842: 4817: 4812: 4806: 4801: 4795: 4790: 4784: 4783: 4776: 4770: 4769: 4767: 4766: 4750: 4744: 4743: 4741: 4739: 4733: 4727:. Archived from 4722: 4713: 4707: 4706: 4696: 4672: 4666: 4665: 4663: 4656: 4647: 4641: 4640: 4638: 4637: 4620:(30 June 2006). 4618:Mark Russinovich 4614: 4608: 4607: 4605: 4604: 4593: 4587: 4586: 4584: 4582: 4576: 4565: 4557: 4551: 4541: 4535: 4528: 4522: 4521: 4493: 4482: 4481: 4479: 4469: 4463: 4457: 4451: 4450: 4448: 4447: 4434: 4410: 4404: 4403: 4385: 4368: 4362: 4356: 4355: 4349: 4341: 4323: 4317: 4311: 4305: 4296:is the key, and 4279: 4273: 4267: 4258: 4252: 4246: 4240: 4231: 4230: 4228: 4227: 4218:. Archived from 4208: 4202: 4201: 4193: 4184: 4178: 4172: 4166: 4155: 4149: 4136: 4135: 4113: 4104: 4085: 4082: 4076: 4069: 3949: 3942: 3938: 3935: 3929: 3898: 3890: 3811: 3809: 3808: 3803: 3774: 3772: 3771: 3766: 3754: 3752: 3751: 3746: 3730: 3728: 3727: 3722: 3667: 3660: 3656: 3653: 3647: 3616: 3608: 3585: 3311: 3304: 3300: 3297: 3291: 3267: 3266: 3259: 3250: 3248: 3247: 3242: 3237: 3233: 3232: 3227: 3216: 3211: 3210: 3193: 3192: 3191: 3163: 3161: 3160: 3155: 3150: 3146: 3142: 3116: 3114: 3113: 3108: 3093: 3091: 3090: 3085: 3056: 3055: 3040: 3039: 3038: 3012: 2994: 2983: 2972: 2894: 2886: 2879: 2875: 2863: 2797: 2789: 2778: 2755: 2748: 2744: 2741: 2735: 2734:for suggestions. 2715: 2714: 2707: 2682: 2681: 2669: 2664: 2653: 2649: 2642: 2631: 2627: 2560: 2558: 2557: 2552: 2534: 2532: 2531: 2526: 2514: 2512: 2511: 2506: 2494: 2492: 2491: 2486: 2474: 2472: 2471: 2466: 2442: 2440: 2439: 2434: 2419: 2417: 2416: 2411: 2399: 2397: 2396: 2391: 2373: 2371: 2370: 2365: 2353: 2351: 2350: 2345: 2333: 2331: 2330: 2325: 2304: 2302: 2301: 2296: 2277:branching factor 2270: 2268: 2267: 2262: 2244: 2242: 2241: 2236: 2224: 2222: 2221: 2216: 2201: 2199: 2198: 2193: 2162: 2160: 2159: 2154: 2141: 2139: 2138: 2133: 2125: 2101: 2099: 2098: 2093: 2074: 2072: 2071: 2066: 2052: 2032: 2030: 2029: 2024: 2016: 1985: 1983: 1982: 1977: 1964: 1962: 1961: 1956: 1948: 1924: 1922: 1921: 1916: 1894: 1892: 1891: 1886: 1859: 1857: 1856: 1851: 1807: 1797: 1795: 1794: 1789: 1787: 1786: 1764: 1762: 1761: 1756: 1754: 1753: 1732: 1730: 1729: 1724: 1722: 1721: 1705: 1703: 1702: 1697: 1695: 1694: 1673: 1671: 1670: 1665: 1663: 1662: 1646: 1644: 1643: 1638: 1636: 1635: 1615: 1567: 1554: 1552: 1551: 1546: 1544: 1543: 1521: 1519: 1518: 1513: 1511: 1510: 1491: 1489: 1488: 1483: 1481: 1480: 1458: 1456: 1455: 1450: 1448: 1447: 1422: 1420: 1419: 1414: 1412: 1411: 1395: 1393: 1392: 1387: 1385: 1384: 1359: 1357: 1356: 1351: 1349: 1348: 1327: 1325: 1324: 1319: 1317: 1316: 1300: 1298: 1297: 1292: 1290: 1289: 1268: 1266: 1265: 1260: 1258: 1257: 1241: 1239: 1238: 1233: 1231: 1230: 1209: 1207: 1206: 1201: 1199: 1198: 1182: 1180: 1179: 1174: 1172: 1171: 1149: 1147: 1146: 1141: 1139: 1138: 1117: 1115: 1114: 1109: 1107: 1106: 1090: 1088: 1087: 1082: 1080: 1079: 1057: 1055: 1054: 1049: 1047: 1046: 1025: 1023: 1022: 1017: 1015: 1014: 998: 996: 995: 990: 988: 987: 965: 963: 962: 957: 955: 954: 933: 931: 930: 925: 923: 922: 906: 904: 903: 898: 896: 895: 875: 803: 789: 787: 786: 781: 763: 761: 760: 755: 753: 752: 730: 728: 727: 722: 720: 719: 695: 693: 692: 687: 675: 673: 672: 667: 665: 664: 646: 644: 643: 638: 636: 635: 614: 612: 611: 606: 604: 603: 581: 435:must be either 2 268:Acta Informatica 215:logarithmic time 203:computer science 171:Space complexity 84: 41: 21: 6131: 6130: 6126: 6125: 6124: 6122: 6121: 6120: 6096: 6095: 6094: 6089: 6076: 6048: 5942: 5938:XOR linked list 5904: 5880:Circular buffer 5861: 5780: 5759: 5757:Data structures 5754: 5724: 5719: 5623: 5502: 5449: 5378: 5374:Weight-balanced 5329:Order statistic 5243: 5235: 5230: 5193: 5186: 5175: 5171: 5164: 5153: 5148: 5137: 5121:Counted B-Trees 5092:B-Tree Tutorial 5082:Wayback Machine 5048: 5031: 5014: 5011: 5009:Original papers 5000: 4980: 4973: 4961:File Structures 4956: 4949: 4933:Stein, Clifford 4919: 4872: 4840: 4828: 4825: 4820: 4813: 4809: 4802: 4798: 4791: 4787: 4778: 4777: 4773: 4764: 4762: 4752: 4751: 4747: 4737: 4735: 4731: 4720: 4715: 4714: 4710: 4674: 4673: 4669: 4661: 4654: 4649: 4648: 4644: 4635: 4633: 4616: 4615: 4611: 4602: 4600: 4595: 4594: 4590: 4580: 4578: 4574: 4563: 4559: 4558: 4554: 4546:, p. 127; 4542: 4538: 4529: 4525: 4518: 4495: 4494: 4485: 4477: 4471: 4470: 4466: 4460:Counted B-Trees 4458: 4454: 4445: 4443: 4412: 4411: 4407: 4400: 4387: 4386: 4371: 4363: 4359: 4342: 4338: 4325: 4324: 4320: 4312: 4308: 4280: 4276: 4268: 4261: 4253: 4249: 4241: 4234: 4225: 4223: 4210: 4209: 4205: 4195: 4194: 4187: 4179: 4175: 4167: 4158: 4150: 4139: 4111: 4106: 4105: 4098: 4094: 4089: 4088: 4083: 4079: 4070: 4066: 4061: 4029: 4017: 4005:red-black trees 4001: 3983: 3978: 3950: 3939: 3933: 3930: 3915: 3899: 3888: 3858:, use B-trees. 3794: 3793: 3757: 3756: 3737: 3736: 3713: 3712: 3709:§ Variants 3705: 3668: 3657: 3651: 3648: 3633: 3617: 3606: 3597: 3517: 3498: 3482: 3445: 3336: 3321: 3312: 3301: 3295: 3292: 3281: 3268: 3264: 3257: 3217: 3202: 3201: 3197: 3176: 3171: 3170: 3134: 3130: 3119: 3118: 3099: 3098: 3047: 3023: 3018: 3017: 3003: 2989: 2978: 2967: 2964: 2939: 2912: 2892: 2888: 2881: 2877: 2871: 2865: 2859: 2855: 2825: 2795: 2791: 2784: 2780: 2776: 2765: 2756: 2745: 2739: 2736: 2729: 2720:This section's 2716: 2712: 2705: 2679: 2667: 2666: 2655: 2651: 2644: 2633: 2629: 2622: 2598: 2570: 2537: 2536: 2517: 2516: 2497: 2496: 2477: 2476: 2475:keys, into two 2448: 2447: 2422: 2421: 2402: 2401: 2376: 2375: 2356: 2355: 2336: 2335: 2307: 2306: 2284: 2283: 2271:is the minimum 2247: 2246: 2227: 2226: 2204: 2203: 2184: 2183: 2177: 2145: 2144: 2110: 2109: 2078: 2077: 2034: 2033: 1989: 1988: 1968: 1967: 1933: 1932: 1901: 1900: 1877: 1876: 1842: 1841: 1830:of child nodes 1829: 1825:of child nodes 1824: 1819: 1814: 1778: 1770: 1769: 1745: 1740: 1739: 1733:does not exist 1713: 1708: 1707: 1686: 1678: 1677: 1654: 1649: 1648: 1627: 1619: 1618: 1606: 1600: 1591: 1585: 1579: 1573: 1535: 1527: 1526: 1502: 1497: 1496: 1472: 1464: 1463: 1433: 1428: 1427: 1403: 1398: 1397: 1370: 1365: 1364: 1340: 1335: 1334: 1328:does not exist 1308: 1303: 1302: 1281: 1273: 1272: 1249: 1244: 1243: 1222: 1214: 1213: 1190: 1185: 1184: 1157: 1152: 1151: 1130: 1122: 1121: 1118:does not exist 1098: 1093: 1092: 1065: 1060: 1059: 1038: 1030: 1029: 1006: 1001: 1000: 973: 968: 967: 946: 938: 937: 914: 909: 908: 887: 879: 878: 866: 860: 854: 845: 839: 833: 827: 821: 815: 809: 766: 765: 738: 733: 732: 711: 706: 705: 678: 677: 656: 651: 650: 627: 619: 618: 595: 587: 586: 579: 557: 536: 504: 415:children and a 395: 388: 381: 374: 367: 360: 308: 247: 221:, allowing for 88:Time complexity 39: 28: 23: 22: 15: 12: 11: 5: 6129: 6127: 6119: 6118: 6113: 6108: 6098: 6097: 6091: 6090: 6088: 6087: 6081: 6078: 6077: 6075: 6074: 6069: 6064: 6058: 6056: 6050: 6049: 6047: 6046: 6045: 6044: 6034: 6033: 6032: 6030:Hilbert R-tree 6027: 6022: 6012: 6011: 6010: 6008:Fibonacci heap 6005: 6000: 5990: 5989: 5988: 5983: 5978: 5976:Red–black tree 5973: 5968: 5958: 5952: 5950: 5944: 5943: 5941: 5940: 5935: 5930: 5925: 5920: 5914: 5912: 5906: 5905: 5903: 5902: 5897: 5892: 5887: 5882: 5877: 5871: 5869: 5863: 5862: 5860: 5859: 5858: 5857: 5852: 5842: 5841: 5840: 5833:Priority queue 5830: 5829: 5828: 5818: 5813: 5808: 5807: 5806: 5801: 5790: 5788: 5782: 5781: 5779: 5778: 5773: 5767: 5765: 5761: 5760: 5755: 5753: 5752: 5745: 5738: 5730: 5721: 5720: 5718: 5717: 5712: 5707: 5702: 5697: 5692: 5687: 5682: 5677: 5672: 5667: 5662: 5657: 5652: 5647: 5642: 5637: 5631: 5629: 5625: 5624: 5622: 5621: 5616: 5611: 5606: 5601: 5596: 5591: 5586: 5581: 5576: 5571: 5566: 5561: 5556: 5539: 5534: 5529: 5524: 5519: 5513: 5511: 5504: 5503: 5501: 5500: 5495: 5490: 5488:Ternary search 5485: 5480: 5475: 5470: 5465: 5459: 5457: 5451: 5450: 5448: 5447: 5442: 5437: 5432: 5427: 5422: 5417: 5412: 5404: 5399: 5394: 5388: 5386: 5380: 5379: 5377: 5376: 5371: 5366: 5361: 5356: 5351: 5346: 5336: 5331: 5326: 5321: 5316: 5311: 5301: 5296: 5291: 5286: 5281: 5276: 5271: 5266: 5261: 5255: 5253: 5237: 5236: 5231: 5229: 5228: 5221: 5214: 5206: 5200: 5199: 5191: 5169: 5146: 5129: 5128: 5123: 5118: 5109: 5104: 5099: 5094: 5089: 5084: 5072: 5066: 5061: 5060:(click "init") 5055: 5052:B-tree lecture 5047: 5046:External links 5044: 5043: 5042: 5029: 5010: 5007: 5006: 5005: 4998: 4978: 4971: 4954: 4947: 4929:Rivest, Ronald 4921:Cormen, Thomas 4917: 4888:(2): 123–137. 4874:Comer, Douglas 4870: 4851:(3): 173–189. 4824: 4821: 4819: 4818: 4807: 4796: 4785: 4771: 4745: 4734:on 4 June 2011 4708: 4687:(4): 650–670. 4667: 4642: 4609: 4588: 4552: 4536: 4523: 4516: 4510:. p. 80. 4508:O'Reilly Media 4483: 4464: 4452: 4405: 4398: 4369: 4367:, p. 488. 4357: 4336: 4318: 4316:, p. 379. 4306: 4274: 4272:, p. 363. 4259: 4257:, p. 362. 4247: 4245:, p. 483. 4232: 4203: 4185: 4173: 4156: 4137: 4095: 4093: 4090: 4087: 4086: 4077: 4063: 4062: 4060: 4057: 4056: 4055: 4050: 4045: 4043:Red–black tree 4040: 4035: 4028: 4025: 4016: 4013: 4000: 3997: 3982: 3979: 3977: 3974: 3952: 3951: 3902: 3900: 3893: 3887: 3884: 3838:, Microsoft's 3823:(and possibly 3801: 3764: 3744: 3720: 3704: 3703:In filesystems 3701: 3670: 3669: 3620: 3618: 3611: 3605: 3602: 3596: 3593: 3592: 3591: 3582: 3581: 3580: 3579: 3578: 3577: 3574: 3568: 3565: 3559: 3558: 3557: 3554: 3551: 3545: 3544: 3543: 3540: 3537: 3516: 3513: 3512: 3511: 3507: 3497: 3494: 3493: 3492: 3489: 3486: 3481: 3478: 3474: 3473: 3470: 3460: 3459: 3455: 3444: 3441: 3368: 3367: 3366: 3365: 3361: 3358: 3352: 3335: 3332: 3320: 3317: 3314: 3313: 3271: 3269: 3262: 3256: 3253: 3252: 3251: 3240: 3236: 3230: 3226: 3223: 3220: 3214: 3209: 3205: 3200: 3196: 3190: 3187: 3184: 3179: 3153: 3149: 3145: 3141: 3137: 3133: 3129: 3126: 3106: 3095: 3094: 3083: 3080: 3077: 3074: 3071: 3068: 3065: 3062: 3059: 3054: 3050: 3046: 3043: 3037: 3034: 3031: 3026: 2963: 2960: 2956: 2955: 2952: 2949: 2946: 2938: 2935: 2923:lazy deletions 2911: 2908: 2890: 2867: 2857: 2824: 2821: 2793: 2782: 2769:order notation 2764: 2761: 2758: 2757: 2719: 2717: 2710: 2704: 2701: 2700: 2699: 2692: 2685: 2618: 2597: 2594: 2569: 2566: 2550: 2547: 2544: 2524: 2504: 2484: 2464: 2461: 2458: 2455: 2432: 2429: 2409: 2389: 2386: 2383: 2363: 2343: 2323: 2320: 2317: 2314: 2294: 2291: 2260: 2257: 2254: 2234: 2214: 2211: 2191: 2176: 2173: 2170: 2169: 2166: 2163: 2152: 2142: 2131: 2128: 2124: 2120: 2117: 2107: 2103: 2102: 2091: 2088: 2085: 2075: 2064: 2061: 2058: 2055: 2051: 2047: 2044: 2041: 2022: 2019: 2015: 2011: 2008: 2005: 2002: 1999: 1996: 1986: 1975: 1965: 1954: 1951: 1947: 1943: 1940: 1930: 1929:Internal node 1926: 1925: 1914: 1911: 1908: 1898: 1895: 1884: 1874: 1871: 1867: 1866: 1863: 1860: 1849: 1839: 1836: 1832: 1831: 1826: 1821: 1816: 1811: 1800: 1799: 1785: 1781: 1777: 1766: 1752: 1748: 1735: 1734: 1720: 1716: 1693: 1689: 1685: 1675: 1661: 1657: 1634: 1630: 1626: 1608: 1607: 1604: 1601: 1598: 1595: 1592: 1589: 1586: 1583: 1580: 1577: 1574: 1571: 1557: 1556: 1542: 1538: 1534: 1523: 1509: 1505: 1493: 1479: 1475: 1471: 1460: 1446: 1443: 1440: 1436: 1424: 1410: 1406: 1383: 1380: 1377: 1373: 1361: 1347: 1343: 1330: 1329: 1315: 1311: 1288: 1284: 1280: 1270: 1256: 1252: 1229: 1225: 1221: 1211: 1197: 1193: 1170: 1167: 1164: 1160: 1137: 1133: 1129: 1119: 1105: 1101: 1078: 1075: 1072: 1068: 1045: 1041: 1037: 1027: 1013: 1009: 986: 983: 980: 976: 953: 949: 945: 935: 921: 917: 894: 890: 886: 868: 867: 864: 861: 858: 855: 852: 849: 846: 843: 840: 837: 834: 831: 828: 825: 822: 819: 816: 813: 810: 807: 795: 794: 791: 779: 776: 773: 751: 748: 745: 741: 718: 714: 698: 697: 685: 663: 659: 648: 634: 630: 626: 616: 602: 598: 594: 584: 556: 555:Node structure 553: 546:) of order 5 ( 535: 532: 503: 500: 481: 480: 468: 464: 463: 456: 453: 401: 400:Internal nodes 393: 386: 379: 372: 365: 358: 352: 351: 350:−1 keys. 340: 337: 334: 327: 307: 304: 246: 243: 231:blocks of data 197: 196: 193: 192: 185: 178: 174: 173: 167: 166: 159: 152: 148: 147: 140: 133: 129: 128: 121: 114: 110: 109: 104: 99: 95: 94: 92:big O notation 80: 79: 70: 66: 65: 62: 58: 57: 52: 46: 45: 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 6128: 6117: 6114: 6112: 6109: 6107: 6104: 6103: 6101: 6086: 6083: 6082: 6079: 6073: 6070: 6068: 6065: 6063: 6060: 6059: 6057: 6055: 6051: 6043: 6040: 6039: 6038: 6035: 6031: 6028: 6026: 6023: 6021: 6018: 6017: 6016: 6013: 6009: 6006: 6004: 6003:Binomial heap 6001: 5999: 5996: 5995: 5994: 5991: 5987: 5984: 5982: 5979: 5977: 5974: 5972: 5969: 5967: 5964: 5963: 5962: 5959: 5957: 5954: 5953: 5951: 5949: 5945: 5939: 5936: 5934: 5931: 5929: 5926: 5924: 5921: 5919: 5916: 5915: 5913: 5911: 5907: 5901: 5900:Sparse matrix 5898: 5896: 5893: 5891: 5888: 5886: 5885:Dynamic array 5883: 5881: 5878: 5876: 5873: 5872: 5870: 5868: 5864: 5856: 5853: 5851: 5848: 5847: 5846: 5843: 5839: 5836: 5835: 5834: 5831: 5827: 5824: 5823: 5822: 5819: 5817: 5814: 5812: 5809: 5805: 5802: 5800: 5797: 5796: 5795: 5792: 5791: 5789: 5787: 5783: 5777: 5774: 5772: 5769: 5768: 5766: 5762: 5758: 5751: 5746: 5744: 5739: 5737: 5732: 5731: 5728: 5716: 5713: 5711: 5708: 5706: 5703: 5701: 5698: 5696: 5693: 5691: 5688: 5686: 5683: 5681: 5678: 5676: 5673: 5671: 5668: 5666: 5665:Hash calendar 5663: 5661: 5658: 5656: 5653: 5651: 5648: 5646: 5643: 5641: 5638: 5636: 5633: 5632: 5630: 5626: 5620: 5617: 5615: 5612: 5610: 5607: 5605: 5602: 5600: 5597: 5595: 5592: 5590: 5587: 5585: 5582: 5580: 5577: 5575: 5572: 5570: 5567: 5565: 5562: 5560: 5557: 5554: 5552: 5546: 5544: 5540: 5538: 5535: 5533: 5530: 5528: 5525: 5523: 5520: 5518: 5515: 5514: 5512: 5509: 5505: 5499: 5496: 5494: 5491: 5489: 5486: 5484: 5481: 5479: 5476: 5474: 5471: 5469: 5466: 5464: 5461: 5460: 5458: 5456: 5452: 5446: 5443: 5441: 5440:van Emde Boas 5438: 5436: 5433: 5431: 5430:Skew binomial 5428: 5426: 5423: 5421: 5418: 5416: 5413: 5411: 5409: 5405: 5403: 5400: 5398: 5395: 5393: 5390: 5389: 5387: 5385: 5381: 5375: 5372: 5370: 5367: 5365: 5362: 5360: 5357: 5355: 5352: 5350: 5347: 5345: 5341: 5337: 5335: 5332: 5330: 5327: 5325: 5322: 5320: 5317: 5315: 5312: 5310: 5309:Binary search 5306: 5302: 5300: 5297: 5295: 5292: 5290: 5287: 5285: 5282: 5280: 5277: 5275: 5272: 5270: 5267: 5265: 5262: 5260: 5257: 5256: 5254: 5251: 5247: 5242: 5238: 5234: 5227: 5222: 5220: 5215: 5213: 5208: 5207: 5204: 5196: 5192: 5185: 5181: 5174: 5170: 5163: 5159: 5152: 5147: 5143: 5142: 5136: 5135: 5134: 5133: 5127: 5124: 5122: 5119: 5117: 5113: 5110: 5108: 5105: 5103: 5100: 5098: 5095: 5093: 5090: 5088: 5085: 5083: 5079: 5076: 5073: 5070: 5067: 5065: 5062: 5059: 5056: 5053: 5050: 5049: 5045: 5038: 5034: 5033:Bayer, Rudolf 5030: 5025: 5022:(July 1970), 5021: 5020:McCreight, E. 5017: 5016:Bayer, Rudolf 5013: 5012: 5008: 5001: 4999:0-201-89685-0 4995: 4991: 4987: 4983: 4982:Knuth, Donald 4979: 4974: 4972:0-201-55713-4 4968: 4963: 4962: 4955: 4950: 4948:0-262-03293-7 4944: 4940: 4939: 4934: 4930: 4926: 4922: 4918: 4913: 4909: 4905: 4901: 4896: 4891: 4887: 4883: 4879: 4876:(June 1979). 4875: 4871: 4866: 4862: 4858: 4854: 4850: 4846: 4839: 4835: 4834:McCreight, E. 4831: 4827: 4826: 4822: 4816: 4811: 4808: 4805: 4800: 4797: 4794: 4789: 4786: 4781: 4775: 4772: 4761: 4760: 4755: 4749: 4746: 4730: 4726: 4719: 4712: 4709: 4704: 4700: 4695: 4690: 4686: 4682: 4678: 4671: 4668: 4660: 4653: 4646: 4643: 4631: 4627: 4623: 4619: 4613: 4610: 4598: 4592: 4589: 4573: 4569: 4568:cs.rhodes.edu 4562: 4556: 4553: 4549: 4545: 4540: 4537: 4533: 4527: 4524: 4519: 4513: 4509: 4505: 4501: 4500: 4492: 4490: 4488: 4484: 4476: 4475: 4468: 4465: 4461: 4456: 4453: 4442: 4438: 4433: 4428: 4424: 4420: 4416: 4409: 4406: 4401: 4395: 4391: 4384: 4382: 4380: 4378: 4376: 4374: 4370: 4366: 4361: 4358: 4353: 4347: 4339: 4337:9780136086208 4333: 4329: 4322: 4319: 4315: 4310: 4307: 4303: 4299: 4295: 4291: 4287: 4283: 4278: 4275: 4271: 4266: 4264: 4260: 4256: 4251: 4248: 4244: 4239: 4237: 4233: 4222:on 2014-06-04 4221: 4217: 4213: 4207: 4204: 4199: 4192: 4190: 4186: 4182: 4177: 4174: 4170: 4165: 4163: 4161: 4157: 4153: 4148: 4146: 4144: 4142: 4138: 4133: 4129: 4125: 4121: 4117: 4110: 4103: 4101: 4097: 4091: 4081: 4078: 4074: 4068: 4065: 4058: 4054: 4051: 4049: 4046: 4044: 4041: 4039: 4036: 4034: 4031: 4030: 4026: 4024: 4022: 4014: 4012: 4010: 4006: 3998: 3996: 3992: 3989: 3980: 3975: 3973: 3971: 3967: 3963: 3959: 3948: 3945: 3937: 3927: 3923: 3919: 3913: 3912: 3908: 3903:This section 3901: 3897: 3892: 3891: 3885: 3883: 3881: 3877: 3876:DragonFly BSD 3873: 3871: 3868: 3864: 3859: 3857: 3853: 3849: 3845: 3841: 3837: 3833: 3828: 3826: 3822: 3818: 3815: 3799: 3791: 3787: 3783: 3779: 3776: 3762: 3742: 3732: 3718: 3710: 3702: 3700: 3697: 3692: 3690: 3684: 3682: 3677: 3666: 3663: 3655: 3645: 3641: 3637: 3631: 3630: 3626: 3621:This section 3619: 3615: 3610: 3609: 3603: 3601: 3594: 3588: 3584: 3583: 3575: 3572: 3571: 3569: 3566: 3563: 3562: 3560: 3555: 3552: 3549: 3548: 3546: 3541: 3538: 3535: 3534: 3532: 3531: 3530: 3527: 3523: 3514: 3508: 3504: 3503: 3502: 3495: 3490: 3487: 3484: 3483: 3479: 3477: 3471: 3468: 3467: 3466: 3463: 3458:restructuring 3456: 3454: 3450: 3449: 3448: 3442: 3440: 3438: 3434: 3430: 3426: 3422: 3416: 3414: 3410: 3406: 3402: 3398: 3394: 3390: 3386: 3382: 3378: 3374: 3362: 3359: 3356: 3355: 3353: 3350: 3349: 3348: 3340: 3333: 3331: 3329: 3328:Binary search 3325: 3318: 3310: 3307: 3299: 3296:February 2012 3289: 3288:the talk page 3285: 3279: 3277: 3272:This article 3270: 3261: 3260: 3254: 3238: 3234: 3228: 3224: 3221: 3218: 3212: 3207: 3203: 3198: 3194: 3177: 3169: 3168: 3167: 3164: 3151: 3147: 3143: 3139: 3135: 3131: 3127: 3124: 3104: 3081: 3078: 3069: 3066: 3063: 3057: 3052: 3048: 3041: 3024: 3016: 3015: 3014: 3010: 3006: 3001: 2996: 2992: 2987: 2981: 2976: 2970: 2961: 2959: 2953: 2950: 2947: 2944: 2943: 2942: 2936: 2934: 2930: 2926: 2924: 2919: 2917: 2909: 2907: 2905: 2901: 2896: 2893:1,000,000 = 3 2884: 2874: 2870: 2862: 2852: 2848: 2845: 2841: 2839: 2833: 2830: 2822: 2820: 2817: 2815: 2810: 2807: 2804: 2799: 2787: 2774: 2773:binary search 2770: 2762: 2754: 2751: 2743: 2733: 2727: 2725: 2718: 2709: 2708: 2702: 2697: 2693: 2690: 2686: 2677: 2673: 2662: 2658: 2647: 2640: 2636: 2625: 2619: 2616: 2612: 2611: 2610: 2608: 2603: 2595: 2593: 2591: 2587: 2586:internal node 2583: 2579: 2573: 2567: 2565: 2562: 2548: 2545: 2542: 2522: 2502: 2482: 2462: 2459: 2456: 2453: 2444: 2430: 2427: 2407: 2387: 2384: 2381: 2361: 2341: 2321: 2318: 2315: 2312: 2292: 2289: 2280: 2278: 2274: 2258: 2255: 2252: 2232: 2212: 2209: 2189: 2180: 2174: 2167: 2164: 2150: 2143: 2126: 2122: 2118: 2108: 2105: 2104: 2089: 2086: 2083: 2076: 2062: 2059: 2053: 2049: 2045: 2039: 2017: 2013: 2006: 2003: 2000: 1987: 1973: 1966: 1949: 1945: 1941: 1931: 1928: 1927: 1912: 1909: 1906: 1899: 1896: 1882: 1875: 1872: 1869: 1868: 1864: 1861: 1847: 1840: 1837: 1834: 1833: 1827: 1822: 1817: 1812: 1809: 1808: 1805: 1783: 1779: 1775: 1767: 1750: 1746: 1737: 1736: 1718: 1714: 1691: 1687: 1683: 1676: 1659: 1655: 1632: 1628: 1624: 1617: 1616: 1602: 1596: 1593: 1587: 1581: 1575: 1569: 1568: 1562: 1540: 1536: 1532: 1524: 1507: 1503: 1494: 1477: 1473: 1469: 1461: 1444: 1441: 1438: 1434: 1425: 1408: 1404: 1381: 1378: 1375: 1371: 1362: 1345: 1341: 1332: 1331: 1313: 1309: 1286: 1282: 1278: 1271: 1254: 1250: 1227: 1223: 1219: 1212: 1210:do not exist 1195: 1191: 1168: 1165: 1162: 1158: 1135: 1131: 1127: 1120: 1103: 1099: 1076: 1073: 1070: 1066: 1043: 1039: 1035: 1028: 1011: 1007: 984: 981: 978: 974: 951: 947: 943: 936: 919: 915: 892: 888: 884: 877: 876: 862: 856: 850: 847: 841: 835: 829: 823: 817: 811: 805: 804: 798: 792: 777: 774: 771: 749: 746: 743: 739: 716: 712: 703: 702: 701: 683: 661: 657: 649: 632: 628: 624: 617: 600: 596: 592: 585: 582: 577: 576: 575: 572: 570: 566: 562: 554: 549: 545: 540: 533: 531: 527: 524: 519: 517: 512: 507: 501: 499: 496: 494: 490: 486: 478: 474: 469: 466: 465: 461: 457: 455:The root node 454: 450: 446: 442: 438: 434: 430: 426: 422: 418: 414: 410: 406: 402: 399: 398: 397: 392: 385: 378: 371: 364: 357: 349: 345: 341: 338: 335: 333:/2⌉ children. 332: 328: 325: 321: 320: 319: 317: 313: 310:According to 305: 303: 301: 297: 293: 289: 285: 281: 277: 272: 270: 269: 264: 260: 256: 252: 244: 242: 240: 236: 232: 228: 224: 220: 216: 212: 208: 204: 190: 186: 183: 179: 175: 172: 168: 164: 160: 157: 153: 149: 145: 141: 138: 134: 130: 126: 122: 119: 115: 111: 108: 105: 103: 100: 96: 93: 89: 85: 81: 78: 74: 71: 67: 63: 59: 56: 53: 51: 47: 42: 37: 33: 19: 5955: 5855:Disjoint-set 5550: 5542: 5407: 5340:Left-leaning 5283: 5246:dynamic sets 5241:Search trees 5140: 5132:Bulk loading 5131: 5130: 5036: 5023: 4985: 4960: 4936: 4885: 4881: 4848: 4844: 4810: 4799: 4788: 4774: 4763:. Retrieved 4757: 4748: 4736:. Retrieved 4729:the original 4724: 4711: 4684: 4680: 4670: 4645: 4634:. Retrieved 4612: 4601:. Retrieved 4591: 4579:. Retrieved 4567: 4555: 4539: 4526: 4498: 4473: 4467: 4455: 4444:. Retrieved 4422: 4418: 4408: 4389: 4360: 4327: 4321: 4309: 4297: 4293: 4289: 4285: 4277: 4250: 4224:. Retrieved 4220:the original 4215: 4206: 4176: 4115: 4080: 4067: 4021:Linux kernel 4018: 4002: 3993: 3984: 3961: 3955: 3940: 3931: 3916:Please help 3904: 3874: 3870:file systems 3860: 3829: 3819: 3780: 3777: 3733: 3706: 3695: 3693: 3688: 3685: 3675: 3673: 3658: 3649: 3634:Please help 3622: 3598: 3586: 3525: 3521: 3518: 3499: 3475: 3464: 3461: 3452: 3446: 3436: 3432: 3431:rather than 3428: 3424: 3420: 3417: 3412: 3408: 3404: 3400: 3396: 3392: 3388: 3384: 3380: 3376: 3372: 3369: 3345: 3326: 3322: 3302: 3293: 3282:Please help 3273: 3165: 3096: 3008: 3004: 2999: 2997: 2990: 2985: 2979: 2968: 2965: 2957: 2940: 2931: 2927: 2920: 2913: 2897: 2882: 2872: 2868: 2860: 2853: 2849: 2846: 2842: 2838:sparse index 2834: 2826: 2818: 2813: 2811: 2808: 2800: 2785: 2766: 2746: 2737: 2721: 2675: 2671: 2660: 2656: 2645: 2638: 2634: 2628:keys, where 2623: 2601: 2599: 2576:data are in 2574: 2571: 2563: 2445: 2281: 2181: 2178: 1803: 1560: 1091:exists, and 796: 699: 578: 573: 568: 564: 560: 558: 528: 522: 520: 515: 510: 508: 505: 497: 492: 488: 484: 482: 476: 472: 459: 448: 444: 440: 436: 432: 428: 424: 420: 416: 412: 408: 390: 383: 376: 369: 362: 355: 353: 347: 343: 330: 323: 315: 309: 299: 295: 291: 287: 283: 279: 278:stands for; 275: 273: 266: 262: 251:Rudolf Bayer 248: 239:file systems 206: 200: 188: 181: 162: 155: 143: 136: 124: 117: 106: 101: 73:Rudolf Bayer 5998:Binary heap 5923:Linked list 5640:Exponential 5628:Other trees 3886:Performance 3790:linked list 2582:disk drives 452:properties. 405:inner nodes 69:Invented by 32:Binary tree 6100:Categories 5986:Splay tree 5890:Hash table 5771:Collection 5584:Priority R 5334:Palindrome 4765:2014-01-27 4738:21 October 4636:2008-04-18 4603:2011-01-17 4544:Comer 1979 4446:2021-08-29 4365:Knuth 1998 4243:Knuth 1998 4226:2011-01-16 4181:Comer 1979 4152:Comer 1979 4092:References 4053:2–3–4 tree 4015:Maple tree 3976:Variations 3676:pre-sorted 3652:April 2018 3506:separator. 3278:to readers 3255:Algorithms 2900:disk cache 2590:disk block 2106:Leaf node 1828:Max number 1823:Min number 1818:Max number 1813:Min number 1810:Node type 1798:is empty. 1555:is empty. 1492:is empty. 548:Knuth 1998 542:A B-tree ( 467:Leaf nodes 306:Definition 233:, such as 107:Worst case 6042:Hash tree 5928:Skip list 5875:Bit array 5776:Container 5670:iDistance 5549:implicit 5537:Hilbert R 5532:Cartesian 5415:Fibonacci 5349:Scapegoat 5344:Red–black 5116:Pat Morin 4904:0360-0300 4830:Bayer, R. 4441:203144646 4346:cite book 3958:skip list 3905:does not 3681:algorithm 3623:does not 3334:Insertion 3213:⁡ 3079:− 3076:⌉ 3058:⁡ 3045:⌈ 2827:A B-tree 2803:seek time 2600:The term 2546:− 2385:− 2130:⌉ 2116:⌈ 2057:⌋ 2043:⌊ 2040:≡ 2021:⌉ 1995:⌈ 1953:⌋ 1939:⌊ 1442:− 1379:− 1166:− 1074:− 982:− 775:≥ 747:− 521:The term 326:children. 235:databases 98:Operation 5971:AVL tree 5850:Multiset 5799:Multimap 5786:Abstract 5685:Link/cut 5397:Binomial 5324:Interval 5184:Archived 5162:Archived 5078:Archived 4984:(1998). 4935:(2001). 4865:29859053 4836:(1972). 4725:dtic.mil 4703:10756181 4659:Archived 4630:Archived 4572:Archived 4292:) where 4132:26930249 4048:2–3 tree 4027:See also 3934:May 2020 3848:Bcachefs 3689:unevenly 3687:them as 3522:rotation 3443:Deletion 3391:−2)/2 = 3235:⌋ 3199:⌊ 3148:⌉ 3132:⌈ 2916:database 2895:reads). 2740:May 2022 2596:Variants 2580:such as 2225:, where 1820:of keys 1815:of keys 565:internal 284:balanced 61:Invented 6025:R+ tree 6020:R* tree 5966:AA tree 5645:Fenwick 5609:Segment 5508:Spatial 5425:Pairing 5420:Leftist 5342:) 5314:Dancing 5307:) 5305:Optimal 4823:Sources 4288:, 4073:sectors 4033:B+ tree 3926:removed 3911:sources 3867:Reiser4 3821:TOPS-20 3644:removed 3629:sources 3274:may be 2914:If the 2689:B+ tree 2615:B+ tree 2613:In the 2607:B+ tree 1674:exists 1269:exists 934:exists 427:−1 and 417:minimum 409:maximum 288:between 245:History 102:Average 36:B+ tree 6106:B-tree 6054:Graphs 6015:R-tree 5956:B-tree 5910:Linked 5867:Arrays 5695:Merkle 5660:Fusion 5650:Finger 5574:Octree 5564:Metric 5498:Y-fast 5493:X-fast 5483:Suffix 5402:Brodal 5392:Binary 4996: 4969: 4945: 4912:101673 4910: 4902: 4863: 4759:GitHub 4701: 4581:24 May 4514: 4439: 4396: 4334: 4130: 4038:R-tree 3968:, for 3966:T-tree 3880:HAMMER 3782:MS-DOS 3526:merged 3364:tree). 3319:Search 2995:keys. 2678:+ 1)/2 2602:B-tree 2443:keys. 2273:degree 1768:Here, 1525:Here, 1462:Here, 1026:exist 298:, and 280:Boeing 207:B-tree 161:O(log 154:O(log 151:Delete 142:O(log 135:O(log 132:Insert 123:O(log 116:O(log 113:Search 44:B-tree 18:B tree 5948:Trees 5821:Queue 5816:Stack 5764:Types 5705:Range 5675:K-ary 5635:Cover 5478:Radix 5463:Ctrie 5455:Tries 5384:Heaps 5364:Treap 5354:Splay 5319:HTree 5274:(a,b) 5264:2–3–4 5187:(PDF) 5176:(PDF) 5165:(PDF) 5154:(PDF) 4908:S2CID 4861:S2CID 4841:(PDF) 4732:(PDF) 4721:(PDF) 4699:S2CID 4662:(PDF) 4655:(PDF) 4575:(PDF) 4564:(PDF) 4478:(PDF) 4437:S2CID 4128:S2CID 4112:(PDF) 4059:Notes 3852:Btrfs 3844:Linux 3825:TENEX 3814:FAT12 3510:node. 2885:= 100 2829:index 2814:block 2792:⌈ log 2781:⌈ log 2637:< 1706:when 1647:when 1301:when 1242:when 1150:when 1058:when 966:when 907:when 516:order 511:order 431:−1). 312:Knuth 300:Bayer 296:bushy 292:broad 223:nodes 177:Space 6037:Trie 5993:Heap 5811:List 5710:SPQR 5589:Quad 5517:Ball 5473:Hash 5445:Weak 5435:Skew 5410:-ary 4994:ISBN 4967:ISBN 4943:ISBN 4900:ISSN 4740:2022 4583:2022 4512:ISBN 4394:ISBN 4352:link 4332:ISBN 3988:ISAM 3964:. A 3909:any 3907:cite 3865:and 3856:ext4 3854:and 3840:NTFS 3836:APFS 3834:and 3832:HFS+ 3696:half 3627:any 3625:cite 3587:Note 3097:Let 2971:≥ –1 2966:Let 2771:. A 2202:and 1594:... 1183:and 999:and 848:... 569:leaf 561:root 523:leaf 447:and 439:or 2 382:and 361:and 253:and 237:and 205:, a 64:1970 50:Type 5845:Set 5715:Top 5569:MVP 5527:BSP 5279:AVL 5259:2–3 4890:doi 4853:doi 4689:doi 4427:doi 4120:doi 3920:by 3878:'s 3863:HFS 3638:by 3435:= 2 3427:= 2 3204:log 3049:log 2982:≥ 0 2891:100 2889:log 2866:log 2856:log 2663:+ 1 2648:- 1 2641:− 1 2626:− 1 2275:or 1605:K-1 1599:K-1 865:K-1 853:K-1 704:If 571:. 419:of 411:of 201:In 90:in 34:or 6102:: 5700:PQ 5614:VP 5604:R* 5599:R+ 5579:PH 5553:-d 5545:-d 5522:BK 5369:UB 5294:B* 5289:B+ 5269:AA 5178:. 5114:, 5018:; 4988:. 4931:; 4927:; 4923:; 4906:. 4898:. 4886:11 4884:. 4880:. 4859:. 4847:. 4843:. 4832:; 4756:. 4723:. 4697:. 4683:. 4679:. 4657:. 4628:. 4624:. 4570:. 4566:. 4506:: 4502:. 4486:^ 4435:. 4423:31 4421:. 4417:. 4372:^ 4348:}} 4344:{{ 4262:^ 4235:^ 4214:. 4188:^ 4159:^ 4140:^ 4126:. 4114:. 4099:^ 4007:, 3872:. 3850:, 3453:OR 3403:=2 3383:=2 3011:–1 3007:= 2993:−1 2798:. 2674:+ 2659:+ 2168:0 2165:0 1897:2 1873:1 1865:0 1862:0 1838:0 1765:. 1597:pr 1582:pr 1570:pr 1522:. 1459:. 1423:. 1360:. 863:pr 857:pt 842:pr 836:pt 824:pr 818:pt 806:pt 563:, 550:). 396:. 294:, 290:, 286:, 282:, 271:. 241:. 187:O( 180:O( 75:, 5749:e 5742:t 5735:v 5619:X 5594:R 5559:M 5555:) 5551:k 5547:( 5543:k 5408:d 5359:T 5338:( 5303:( 5299:B 5284:B 5252:) 5248:/ 5244:( 5225:e 5218:t 5211:v 5041:. 5028:. 5002:. 4977:. 4975:. 4951:. 4916:. 4914:. 4892:: 4869:. 4867:. 4855:: 4849:1 4782:. 4768:. 4742:. 4705:. 4691:: 4685:6 4639:. 4606:. 4585:. 4534:. 4520:. 4449:. 4429:: 4402:. 4354:) 4340:. 4298:a 4294:x 4290:a 4286:x 4229:. 4171:. 4154:. 4134:. 4122:: 3962:n 3947:) 3941:( 3936:) 3932:( 3928:. 3914:. 3800:i 3763:i 3743:i 3719:i 3665:) 3659:( 3654:) 3650:( 3646:. 3632:. 3437:L 3433:U 3429:L 3425:U 3421:U 3413:L 3409:L 3405:L 3401:U 3397:U 3393:L 3389:U 3385:L 3381:U 3377:U 3373:U 3309:) 3303:( 3298:) 3294:( 3290:. 3239:. 3229:2 3225:1 3222:+ 3219:n 3208:d 3195:= 3189:x 3186:a 3183:m 3178:h 3152:. 3144:2 3140:/ 3136:m 3128:= 3125:d 3105:d 3082:1 3073:) 3070:1 3067:+ 3064:n 3061:( 3053:m 3042:= 3036:n 3033:i 3030:m 3025:h 3009:m 3005:n 3000:h 2991:m 2986:m 2980:n 2969:h 2883:b 2878:b 2873:N 2869:b 2861:N 2858:2 2794:2 2788:⌉ 2786:N 2783:2 2777:N 2753:) 2747:( 2742:) 2738:( 2728:. 2680:⌋ 2676:j 2672:m 2670:( 2668:⌊ 2661:j 2657:m 2652:j 2646:m 2639:m 2635:j 2630:m 2624:m 2549:1 2543:d 2523:d 2503:d 2483:d 2463:1 2460:+ 2457:d 2454:2 2431:d 2428:2 2408:d 2388:1 2382:d 2362:d 2342:d 2322:1 2319:+ 2316:d 2313:2 2293:d 2290:2 2259:1 2256:+ 2253:d 2233:d 2213:d 2210:2 2190:d 2151:K 2127:2 2123:/ 2119:K 2090:1 2087:+ 2084:K 2063:1 2060:+ 2054:2 2050:/ 2046:K 2018:2 2014:/ 2010:) 2007:1 2004:+ 2001:K 1998:( 1974:K 1950:2 1946:/ 1942:K 1913:1 1910:+ 1907:K 1883:K 1848:K 1784:i 1780:r 1776:p 1751:i 1747:k 1719:i 1715:k 1692:i 1688:r 1684:p 1660:i 1656:k 1633:i 1629:r 1625:p 1603:k 1590:1 1588:k 1584:1 1578:0 1576:k 1572:0 1541:i 1537:r 1533:p 1508:i 1504:k 1478:i 1474:t 1470:p 1445:1 1439:i 1435:k 1409:i 1405:k 1382:1 1376:i 1372:k 1346:0 1342:k 1314:i 1310:k 1287:i 1283:r 1279:p 1255:i 1251:k 1228:i 1224:r 1220:p 1196:i 1192:k 1169:1 1163:i 1159:k 1136:i 1132:t 1128:p 1104:i 1100:k 1077:1 1071:i 1067:k 1044:i 1040:t 1036:p 1012:i 1008:k 985:1 979:i 975:k 952:i 948:t 944:p 920:0 916:k 893:0 889:t 885:p 859:K 851:k 844:1 838:2 832:1 830:k 826:0 820:1 814:0 812:k 808:0 790:. 778:1 772:i 750:1 744:i 740:k 717:i 713:k 696:. 684:i 662:i 658:k 633:i 629:r 625:p 601:i 597:t 593:p 580:K 493:n 489:U 485:n 477:m 473:m 460:L 449:L 445:U 441:L 437:L 433:U 429:U 425:L 421:L 413:U 394:2 391:a 387:2 384:a 380:1 377:a 373:1 370:a 366:2 363:a 359:1 356:a 348:k 344:k 331:m 324:m 316:m 276:B 191:) 189:n 184:) 182:n 165:) 163:n 158:) 156:n 146:) 144:n 139:) 137:n 127:) 125:n 120:) 118:n 38:. 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.