An Introduction to Btrees

Table of Contents

Outline

Motivation

Motivation (cont.)

Multiway Search Trees (of order m)

Multiway Search Trees (cont.)

Definition of a B-Tree

Insertion in a B-Tree

Insertion in a B-Tree (pseudo code)

Deletion From a B-Tree

Deletion From a B-Tree (cont.)

Deletion From a B-Tree (cont.)

Deletion From a B-Tree (pseudo code)

Miscellaneous

Height of a B-tree

Height of a B-tree (cont.)

Height of a B-tree (cont.)

Height of a B-tree (cont.)

Height of a B-tree (cont.)

Height of a B-tree (cont.)

Height of a B-tree (numerical example)

Email: f.maire@qut.edu.au

Home Page: http://www.fit.qut.edu.au/~maire