Design and Analysis of Algorithms: B-Trees

Overview

Balanced search trees designed to work well on secondary storage devices.

Number of children: A few, or thousands!
O(lg n) performance.
If an internal node contains n keys, then it has n + 1 children. We make an n + 1 way decision when reaching this node in search.

Data structures on secondary storage

The big difference: We might be able to perform 100,000 accesses of primary memory in the time ot takes to find the proper place to start a disk read.

Definition of B-trees

The height of a B-tree

Basic Operations on B-trees

Searching a B-Tree

Creating an empty B-Tree

Inserting a key into a B-Tree

Splitting a node in a B-tree

Inserting a key into a B-Tree in a single pass down the tree

Deleting a key from a B-tree

Source Code

Python