Editing B-tree (section)

===Index performance===
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>