Algorithms and Data Structures: 2-3-, 2-3-4-, B-Trees

[CSE2304], [FAQ], [progress] & [plan], Bib', Alg's, C - L.A., Sem'1, 2006, FIT, Monash, .au
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Tables: 2-3-, 2-3-4- & B-Trees: Introduction

Yet more tree structures for implementing lookup tables:

Height balanced, operations have O(log(n))-time complexity.

B-trees are very important for large (disc) collections (data-bases).

Binary search tree (and AVL tree) have

one element, two sub-tree pointers, per `fork' node,
therefore no spare room for more elements in forks,
so new elements are inserted in new leaves.

2-3-trees have

one or two elements per fork, up to three sub-tree pointers
Ptr_1 Elt_1 Ptr_2 Elt_2 Ptr_3
so a fork node may be full or only half full
New elements can be added to internal fork nodes.

NB. Ordered left-right like a BST.
NB. Two kinds of 2-3-tree:
1. elements proper go in fork nodes or
2. fork nodes form an index to "real" elements (elsewhere).

2-3-tree, insert an element:

First search (left/middle/right) to find the appropriate fringe node, then
if space in the node, add index-element and (data-)pointer
else node full:
- i.e. would have 4 pointers (and 3 index-elements), so must split the node:
- divide pointers across old node and new node, and . . .
- add pointer to new-node (and index-element) to parent . . .
- which might split . . .
- etc. (possibly up to root)

[lecturer: do insertion examples; class: take notes!]

2-3-tree:

grows at the top when (if) root splits
is always perfectly height balanced

because [_____________________]
element space from 50% to 100% occupied

2-3-4-tree:

room for 3 elements and
4 pointers per fork node

Ptr_1

Elt_1

Ptr_2

Elt_2

Ptr_3

Elt_3

Ptr_4

Insertion can be as for 2-3-tree
possibly splitting up to root, or . . .

2-3-4-tree

. . . it is possible to keep splitting "local"
by keeping some "spare room" low down the tree
which means insert can be iterative (v. recursive).

This is done by:

splitting any 4-nodes during descent
which guarantees that every 4-node has a 2- or 3-node as parent

[lecturer: draw diagram; class: take notes!]

B-tree of order-k is the logical generalisation of 2-X-trees.

All internal nodes (except perhaps the root) have between ceiling(k/2) and k sub-trees (and one fewer elements).
All leaves are at the same depth
height is O( log_k(n) )
i.e. height decreases as k increases

log₂ (1,000,000) = _________

log₁₀ (1,000,000) = _________

log₁₀₀ (1,000,000) = _________

The B-tree structure is popular for very large data sets

especially stored on disc
make order, `k', as large as possible

(often to fit disc block size)
want to reduce slowest operation
i.e. reduce # of disc accesses

Tables: 2-3-, 2-3-4- & B-Trees: Summary

2-3- and 2-3-4-trees are special case of B-tree
possible to ensure only "local" changes on insert for 2-3-4- and higher order -trees.
High order, k, good for B-tree on disc.

Prepare

String searching algorithms