B-Trees

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

Algorithms
 glossary
 Binary Trees
  Search T'
  23trees
  234trees
  Btrees
  Tries
  PATRICIA
  Suffix Trees

 Tables
C
o
m
p
u
t
e
r
-
S
c
i
e
n
c
e

A B-tree of order n is a generalisation of [2-3-trees], [2-3-4-trees] (and sort-trees) in which each node has at least ceiling(n/2) elements and at most n elements. A B-tree is height-balanced and search, insert and delete times are O(lognN). This decreases as n increases. The B-tree is often used in data-base applications where the dominant cost is that of reading forks into main memory; once in main memory, operations are (relatively) fast. Often, n is determined by the size of elements (or keys) and the size of one disc block, there being one node per block.

fork:  [|,k1,|,k2,|, ..., kn,|]
        |    |    |          |
        |    |    |          |
        |    |    v          v
        |    v    c2         cn
        v    c1
        c0

ki is the least key in ci,
ki < ki+1

leaf:      k1,k2, ..., kn

As for the 2-3-tree, if a node is partially full a new child can be added easily, while maintaining the sortedness property. If a node should overflow, it is split. A new node is created and half of the full node copied into it. The new node is now inserted into the original node's parent; this may cause further splits. If the root is split then a new root is created and the B-tree grows one level taller.


[|,10,|,-,/,-,/,-,/]
 |    |
 |    |
 |    [10,11,12,13]
 |
 1,2,-,-

add 14:
[|,10,|,13,|,-,/,-,/]
 |    |    |
 |    |    |
 |    |    [13,14,-,-]
 |    |
 |    [10,11,12,-]
 |
 [1,2,-,-]

Notes

  • Many variations are possible, e.g.
    • Data entries "proper" (i.e. key plus associated information) can all be placed in external leaf nodes only, as in the examples above, in which case the tree is an index into the data proper, or
    • data entries can be placed in internal nodes also.
    • Splitting of over-full nodes can propagate backwards up the B-tree as far as necessary (as above, and natural with recursion), or
    • nodes that are exactly full can be split on the way down the tree in case they would otherwise have had to be split later.
  • See
    • N. Wirth, Algorithms + Data-Structures = Programs, Prentice Hall 1976, p245, and also Algorithms and Data Structures, Prentice Hall 1986, p241.
    • R. Sedgewick. Algorithms in C (1st edn), Addison Wesly 1990, ch18, p262.
    • M. A. Weiss. Data Structures and Algorithm Analysis in C, sec4.7 p133, Addison Wesley, 1997.
  • Search for Btree in the [bibliography].


L. A. 1986, Department of Computer Science, Monash University, 1984, and (HTML) School of Comp Sci and Software Engineering, 1999.
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 22-Aug-2014 00:03:52 EST.