Choose Index below for a list of all words and phrases defined in this glossary.

B Tree / B-Tree

index | Index

B Tree / B-Tree - definition(s)

B Tree - An indexing technique in which pointers to data are kept in a Balanced Tree structure such that all referenced data is equally accessible in an equal time frame. For example, this would allow an alphabetical search on names to access the names Adams, Madison and Young with equal speed.

[Category=Data Warehousing ]

Source:, 18 July 2010 08:54:52, External

These advertisers support this free service

B Tree - An indexing technique in which pointers to data are kept in a Balanced Tree structure such that all referenced data is equally accessible in an equal timeframe. It is also a tree data structure which keeps data sorted so that searching, inserting and deleting can be done in logarithmic amortized time.

[Category=Data Warehousing ]

Source: Aexis Business Intelligence, 03 November 2010 08:43:28, External

B-tree - [data structures] A tree data structure used for indexing data within a database or file system implementation. In a B-tree structure, data is sorted into a set of hierarchical nodes, usually using only three or four levels. The limited number of levels makes effective searches possible, because most of the nodes in the tree do not have to be accessed during a search.

[Category=Geospatial ]

Source: esri, 06 February 2012 07:33:15, External 

B-tree - A B-tree is a method of placing and locating files (called records or keys) in a database. (The meaning of the letter B has not been explicitly defined.) The B-tree algorithm minimizes the number of times a medium must be accessed to locate a desired record, thereby speeding up the process.

B-trees are preferred when decision points, called nodes, are on hard disk rather than in random-access memory (RAM). It takes thousands of times longer to access a data element from hard disk as compared with accessing it from RAM, because a disk drive has mechanical parts, which read and write data far more slowly than purely electronic media. B-trees save time by using nodes with many branches (called children), compared with binary trees, in which each node has only two children. When there are many children per node, a record can be found by passing through fewer nodes than if there are two children per node. A simplified example of this principle is shown below.


In a tree, records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. The maximum number of children per node is the order of the tree. The number of required disk accesses is the depth. The image at left shows a binary tree for locating a particular record in a set of eight leaves. The image at right shows a B-tree of order three for locating a particular record in a set of eight leaves (the ninth leaf is unoccupied, and is called a null). The binary tree at left has a depth of four; the B-tree at right has a depth of three. Clearly, the B-tree allows a desired record to be located faster, assuming all other system parameters are identical. The tradeoff is that the decision process at each node is more complicated in a B-tree as compared with a binary tree. A sophisticated program is required to execute the operations in a B-tree. But this program is stored in RAM, so it runs fast.

In a practical B-tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but at least half of them do. The difference in depth between binary-tree and B-tree schemes is greater in a practical database than in the example illustrated here, because real-world B-trees are of higher order (32, 64, 128, or more). Depending on the number of records in the database, the depth of a B-tree can and often does change. Adding a large enough number of records will increase the depth; deleting a large enough number of records will decrease the depth. This ensures that the B-tree functions optimally for the number of records it contains.

Also see tree structure. Compare binary tree, M-tree, splay tree, and X-tree.

Related glossary terms: Binary Large Object (BLOB), data structure, catalog, data mart (datamart), ECMAScript (European Computer Manufacturers Association Script), Visual FoxPro, segment, block, flat file

[Category=Data Management ]

Source:, 06 July 2013 09:25:16, External  





Data Quality Glossary.  A free resource from GRC Data Intelligence. For comments, questions or feedback: