B-tree


Also found in: Acronyms, Wikipedia.

B-tree

[′bē ‚trē]
(computer science)

B-tree

(algorithm)
A multi-way balanced tree.

The "B" in B-tree has never been officially defined. It could stand for "balanced" or "Bayer", after one of the original designers of the algorithms and structure. A B-tree is _not_ (necessarily?) a "binary tree".

A B+-tree (as used by IBM's VSAM) is a B-tree where the leaves are also linked sequentially, thus allowing both fast random access and sequential access to data.

[Knuth's Art of Computer Programming].

B-tree

(Balanced-tree) A technique for organizing indexes. In order to keep access time to a minimum, B-tree stores the data keys in a balanced hierarchy that continually realigns itself as items are inserted and deleted. Thus, all nodes always have a similar number of keys.

B+tree is a version of B-tree that maintains a hierarchy of indexes while also linking the data sequentially, providing fast direct access and fast sequential access. The IBM mainframe VSAM access method uses the B-tree method. See Btrfs and VSAM.
References in periodicals archive ?
Starting with B-Tree, people have already used cache to temporarily store pages in memory, which greatly reduces I/O.
The structural features of common indexes, such as the B-tree or hashed table enforce highly precise localisation to achieve the best possible search efficiency.
Then a query of the form "provide the history of key k after (before) time t" is addressed by first finding k (using hashing or the B-tree) and then locating the version of k that is closest to transaction time t using the multilevel index on k's versions.
The tree on W2 and the b-tree on W3, though they do not share their "coexistence properties" (properties having to do with coexisting or not coexisting with some other tree and all the properties that come along with these) and though they cannot, without begging the question, be assumed to share their "identity properties" (properties like being identical to t), do share all their other properties.
B-tree is used to construct the location indexes with the directions X and Y on the anonymous server.
Hash organised tables are, in short, for static data, while B-trees might be used more appropriately for both systems as they provide good concurrency and flexible queries.
This approach, which has become popular with the B-tree, is based on the assumption that most searches are I/O-bound rather than CPU-bound--an assumption that is not always true in spatial data management, however.
This assured that after a search, such as a Prefix B-Tree search, if the search key was not found, then the position found was the correct place to insert a new entry.
Another important tuning feature in SR2 is the addition of multi-key compound indexes (B-tree).
The Merkle B-tree (MB-tree) [8] is an improved MH-tree where the node fanout is determined by the PC's block size, motivated by the idea of the B+-tree.
For large tables with dynamic data, such as a fact table, B-Tree indexes and hashed clusters are unsuitable.