[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:24:09 AEDT
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!]

• 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( logk(n) )

• i.e. height decreases as k increases

log2 (1,000,000) = _________

log10 (1,000,000) = _________

log100 (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

© L.Allison, Sunday, 28-Nov-2021 04:24:09 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/12.234B.shtml
Computer Science, Software Engineering, Science (Computer Science).