Indexing

5.1 B-Trees and B+ Trees

B-Tree of order $m$. A balanced search tree where each internal node has between $\lceil m/2 \rceil$ and $M$ children. All leaves are at the same depth.

Properties:

• Root: at least 2 children (unless it is a leaf).
• Internal node with $k$ children has $k - 1$ keys.
• All leaves at the same depth $h$.
• Height: $h = O(\log_m n)$.

Operations:

• Search: $O(\log_m n)$. At each node, binary search the keys and follow the appropriate child pointer.
• Insert: Find the correct leaf. If the leaf has room, insert. If full, split the leaf and propagate the median key up. May cascade splits to the root.
• Delete: Find the key. If in an internal node, replace with predecessor/successor and delete from the leaf. If a node underflows (fewer than $\lceil m/2 \rceil - 1$ keys), redistribute from a sibling or merge with a sibling.

B+ Tree. Variant where:

• All data records are stored only in leaf nodes (internal nodes store only keys for routing).
• Leaf nodes are linked in a linked list for efficient range queries.

This makes B+ trees the standard for database indexing. The linked leaf list allows range scans in $O(\log_m n + k)$ where $k$ is the number of records in the range.

B+ Tree insert pseudocode:

def bplus_insert(root, key, value):
    leaf = find_leaf(root, key)
    insert_into_leaf(leaf, key, value)
    if len(leaf.keys) > MAX_KEYS:
        new_leaf, median = split_leaf(leaf)
        insert_into_parent(leaf.parent, median, new_leaf)

Internal: [10]
  ├── Leaf: [5]
  └── Leaf: [10, 20]

Internal: [10, 15]
  ├── Leaf: [5]
  ├── Leaf: [10, 15]
  └── Leaf: [20]

Root: [15]
  ├── Internal: [10]
  │     ├── Leaf: [5]
  │     └── Leaf: [10, 15]
  └── Internal: [25]
        ├── Leaf: [20, 25]
        └── Leaf: [30]

Root: [15]
  ├── Internal: [10]
  │     ├── Leaf: [5]
  │     └── Leaf: [10, 15]
  └── Internal: [30]
        ├── Leaf: [20]
        └── Leaf: [30]

Root: [30]
  ├── Leaf: [5]
  ├── Leaf: [10]     (originally contained 10 before deletion)
  └── Leaf: [30]

5.2 Hash Indexes

Static hashing. A hash function $h : K \to \\{0, \ldots, B - 1\\}$ maps keys to $B$ buckets. Average lookup: $O(1)$ under uniform hashing. No support for range queries.

Collision handling. When two keys hash to the same bucket, the DBMS must resolve the collision:

1. Separate chaining: Each bucket contains a linked list of entries. Lookup requires traversing the chain. Average chain length under uniform hashing is $n / B$.
2. Open addressing (linear probing): If bucket $h(k)$ is full, try $h(k)+1$, $h(k)+2$Etc. (mod $B$). Prone to primary clustering: consecutive occupied slots increase the average probe length.
3. Open addressing (quadratic probing): Try $h(k) + 1^2, h(k) + 2^2, h(k) + 3^2$Etc. Reduces clustering but may not probe all buckets.
4. Open addressing (double hashing): Use a second hash function $h_2$: probe sequence is $h(k) + i \cdot h_2(k)$ for $i = 0, 1, 2, \ldots$. Minimises clustering.

Extendible hashing. Dynamically grows the number of buckets. Uses a global depth $d$ and Per-bucket local depth $d'$.

• Hash key to $d$ bits.
• If the bucket is full and its local depth equals the global depth, double the directory (global depth increases by 1) and split the bucket.
• If the bucket’s local depth is less than the global depth, split the bucket without doubling the directory.

Linear hashing. Gradually grows one bucket at a time using a pointer to the next bucket to split. Simpler than extendible hashing but may have slightly higher overflow probability.

Comparison:

5.3 Bitmap Indexes

A bitmap index creates one bitmap per distinct value of an attribute. For a table with $n$ rows And attribute $A$ with values $\\{v_1, \ldots, v_k\\}$Store $k$ bitmaps of $n$ bits each, where Bitmap $i$ has a 1 in position $j$ if row $j$ has $A = v_i$.

Use case: Low-cardinality columns (gender, status, country). Bitmap indexes support fast bitwise AND/OR for multi-criteria queries.

Bitwise operations for query evaluation:

Compression. For columns with many distinct values, run-length encoding (WAH or BBC) compresses Bitmaps effectively while still supporting bitwise operations.

5.4 Query Processing Cost Estimation

The cost model estimates the number of disk I/O operations for a query plan. We assume the buffer Pool has $B$ pages and each disk page access costs one I/O.

Selection cost estimation:

Where $f$ is the fanout (average number of children per internal node).

Join cost estimation (from Section 7):