Table Index

a replica of a subset of a table's attributes that are organized and/or sorted for efficient access using a subset of those attributes.

The DBMS ensures that the contents of the table and the index are logically in sync.

1. B+Tree Overview

<aside> 💡 B-Tree Family

• B-Tree (1971)
• B+Tree (1973)
• B*Tree (1977?)
• Blink-Tree (1981)

The B+Tree in DBMS is not only the 1973 B+Tree

</aside>

A B+Tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in O(log n).

• Generalization of a binary search tree in that a node can have more than two children.
• Optimized for systems that read and write large blocks of data.

1.1 Properties

A B+Tree is an $M$-way search tree with the following properties:

• It is perfectly balanced (i.e., every leaf node is at the same depth).
• Every node other than the root, is at least half-full

$$ \gdef\M{\hbox{M}} \hbox{Degree(\#keys)} \in

\left[\frac\M 2 - 1,\M - 1\right] $$

• Every inner node with $k$ keys has $k+1$ non-null children

Inner nodes have pointers, leaf nodes have data

Every B+Tree node is comprised of an array of key/value pairs.

• The keys are derived from the attributes(s) that the index is based on.
• The values will differ based on whether the node is classified as inner nodes or leaf nodes.