Advanced Data Structure
BTree
Btrees are balanced search trees designed to work well on disks or other directaccess secondary storage devices. Btrees are similar to redblack trees, but they are better at minimizing disk I/O operations. Many database systems use Btrees, or variants of Btrees, to store information.
Btrees differ from redblack trees in that Btree nodes may have many children, from a few to thousands. That is, the “branching factor” of a Btree can be quite large, although it usually depends on characteristics of the disk unit used. Btrees are similar to redblack trees in that every nnode Btree has height O.lg n/. The exact height of a Btree can be considerably less than that of a redblack tree, however, because its branching factor, and hence the base of the logarithm that expresses its height, can be much larger. Therefore, we can also use Btrees to implement many dynamicset operations in time O(lgn).
Definition of Btrees
minimum degree t

Every node other than the root must have at least t  1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.

Every node may contain at most 2t  1 keys. Therefore, an internal node may have at most 2t children. We say that a node is full if it contains exactly 2t  1 keys.
Basic operations on Btrees
Searching a BTree
Insertion
Before we can insert, we need to know how to split a full node:
Deletion
There are so many cases: