Topic: b-trees

topics > computer science > data > Group: data structures

database keys and indexing
external search and sort
full-text indexing
relational database
search algorithms
sort algorithms


A B-tree is an index structure for disk-based data. It features height-balanced trees with a high branching factor. The index is sorted and allows concurrent access and update. Elementary operations use at most two physical accesses to disk.

B-trees are widely used to implement relational database systems. A B-tree may replace file directories. Extensions include time-split B-trees and multidimensional B-trees. (cbb 6/06)

Subtopic: B-trees up

Quote: B-trees split and merge at leaves; height increases or decreases at root; overflow between two adjacent brothers [»bayeR_1972]
Quote: B+-trees are nearly optimal for disk-based indices; good storage utilization [»bayeR_1972]
Quote: B-trees widely used to implement relational database systems; primary commercial application [»bayeR_2002]
Quote: each B-tree level increases size by 400x; at most two physical I/O per operation due to caching highest levels [»bayeR_2002]

Subtopic: metadata as B-tree up

Quote: GFS uses a B-tree to map namespace to metadata; no directory nodes; 100 bytes per file [»gherS10_2003]
Quote: each GFS namespace node has a read-write lock; consistent total order to prevent deadlock

Subtopic: concurrent processing up

Quote: for concurrent operations on B-trees, separate safe from unsafe nodes; an update to a safe node does not affect its ancestors [»bayeR_1977]
Quote: algorithm for concurrent, tunable indexing of B*-trees; deadlock free [»bayeR_1977]

Subtopic: time-split B-trees up

Quote: time-split B-trees allow concurrent updates via short, independent atomic actions [»lomeD_1993]
Quote: with time-split b-trees, read-only transactions only need a timestamp for concurrency control; ignores all later records [»lomeD6_1989]
Quote: time-split b-tree partitions data into historical data on write-once media and current data; can have copies in both partitions [»lomeD6_1989]
Quote: time-split B-trees are space and time efficient; the fraction of redundant records is bounded [»lomeD_1993]
Quote: based time-split b-trees on Easton's write-once b-trees [»lomeD6_1989]
Quote: use time-split B-tree (TSB-tree) for time-slice queries of a transaction-time database; data clustered by time-slice and key; replicate historical versions as needed; store on WORM disk [»lomeD_1993]

Subtopic: multidimensional B-tree up

Quote: the UB-Tree uses a space-filling curve to map multidimensions into one; the Z-curve is efficiently implemented as variable length bitstrings [»ramsF9_2000, OK]
Quote: the R-tree is a multi-dimensional index by bounding boxes; like the B-tree; efficient for points and regions

Related Topics up

Topic: database keys and indexing (18 items)
Topic: external search and sort (23 items)
Topic: full-text indexing (37 items)
Topic: relational database (35 items)
Topic: search algorithms (40 items)
Topic: sort algorithms (24 items)
Topic: trees
(21 items)

Updated barberCB 4/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.