B-Tree | Research & Encyclopedia Articles

B-Tree

A B-tree is a type of balanced tree. A tree is defined as a data structure in which access always begins from the "root node," where a "node" is simply a reference point in the tree, and the "root node" is the only node that has no parent. The end-points of the tree comprise nodes that have no "child nodes," and these are called the "leaves"; nodes that do have child nodes are called "interior nodes." A balanced tree is a special kind of tree where all the leaves are all a similar distance from the root node. Unlike the kind of tree that grows in the ground, data trees are typically represented with the root at the top with the branches fanning out below it.

A B-tree is an efficient means of storing and finding records in a database. The B-tree algorithm minimises the frequency of accesses to the database itself when locating a given record, and so makes the process more efficient and quicker. B-trees are superior to other types of trees when the database to be searched and updated is external to the main memory of the computer, because access to peripherals like disc drives and networks is several orders of magnitude slower than access to the computer's main memory store.

B-trees are faster because they use nodes with many child nodes or "branches." This is in contrast to binary trees, where each node has only two branches. Having several branches per node means that a record can be located in the database by iterating over fewer nodes than if there are only two branches per node as in a binary tree. This makes searching a B-tree faster when the access time per node is slow, as it often is when the storage medium is located outside of the main computer. The maximum number of branches per node is called the "order" of the tree, and the number of required accesses to reach a leaf is called the tree's "depth."

The search algorithm for a B-tree runs in logarithmic time; that is, the average time to find an entry in a tree with depth "n" is O(log n). In both binary trees and B-trees, the data records are always stored at the leaves. So for a binary tree to store 128 records, it will require a depth of 7 because 2⁷ is 128. A B-tree of order 3, on the other hand, will require a depth of only 5, since 3⁵ is 243. A depth of 4 would allow a B-tree of order 3 to store only 81 records, because 3⁴ is 81.

While the B-tree allows a given record to be found more quickly than in a binary tree, all other things being equal, there is compromise in efficiency because the decision process at each node is far more complicated in a B-tree than it is in a binary tree. For this reason, when node-access is fast, as it is if the entire tree is held in memory, binary trees are faster.

In a practical B-tree there may be many millions of records. Not every leaf has to contain a record, but at least half of them will. The difference in depth between practical binary-trees and practical B-trees can be very large indeed because real-world B-trees are sometimes of order 128 or more, and an equivalent binary tree will have a much larger depth and hence a much longer search time.

The depth of a B-tree will change if a large enough number of records is added to it; conversely, the depth will decrease if large enough number of records is deleted. The effect of this is to ensure that the B-tree is always optimally configured for the number of records it contains.