### B-Trees

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

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

Tables
 Computer -Science

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,-,-

```
```[|,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:
 The Darwin Awards V: Next Evolution

 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 Wednesday, 12-Aug-2020 10:43:48 AEST.