B-tree

(redirected from B-trees)

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 ?
Concurrent cache-oblivious B-trees. In Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages 228-237, ACM, New York, U.S.A.
Popular document stores use B-Trees to index documents in the DBMS rather like an advanced filing cabinet.
It provides theoretical explanations for new systems, techniques, and databases like GFS and HDFS (Google and Hadoop file systems), MapReduce, Cassandra, Neo4j, and MongoDB; outlines traditional algorithms like mergesort, B-trees, and hashing; discusses the foundations of different technologies and use cases for them; and details physical storage hardware like hard disk drives, solid-state drives, and magnetoresistive RAM to understand how they function and affect the complexity, performance, and capabilities of existing storage and analytics algorithms.
New features enhancing this revised sixth edition include range-based for loops and threads; Trees Plus, that emphasizes balancing of search trees by covering AVL Trees, Red-Black Trees, and B-Trees; a new chapter on Sets, Maps, and Hashing; Sorting, which now includes practical performance issues and parallel merge sort; and new chapters in the second half of the text that are now easier to assign in alternate orders, supporting a wider range of course goals and organizations.
We disconfirmed in our research that cache coherence and B-trees can interfere to surmount this question, and our methodology is no exception to that rule.
We can see that there are extended B-trees for the timestamp in the bottom level and the fixed network R-tree in the top level.
As we have already seen, the precision of B-trees and hashed tables are similar and exhibit similar maintenance costs despite having very different clustering characteristics.
The recommended way to do this is the method described by Bayer and Unterauer in "Prefix B-Trees" [2].
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.
New observations are made about B-trees and F-heaps.
B-trees, on the other hand, can be appropriate to both applications offering both good concurrency and flexible queries; but they must be used with care on heavily updated tables of significant size, since they can become rapidly disk I0 bound and can cause excessive database checkpoint activity.
Virtually all of the over 100 implementations of MUMPS maintain files as self-optimizing B-Trees and do not require any preallocation of disk space.