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]

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

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]

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]

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 [»shasD_2004]