Indexing | Computer Science - Wyatt's Notes

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]

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:

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.

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):

Indexes are the lookup tables that make database queries fast, like the index at the back of a textbook that tells you which page discusses a topic. Without an index, every query scans every row (a full table scan), which is like reading an entire book to find one fact. B-tree indexes organize data in a balanced tree structure that allows logarithmic lookup, the way a phone book is organized alphabetically so you can find any name in about 20 steps regardless of whether the book has 1,000 or 1,000,000 entries.

Assuming more indexes always improve performance: Indexes speed up reads but slow down writes (each insert/update must update indexes). Over-indexing degrades write performance. Choose indexes wisely.

Confusing clustered with non-clustered indexes: A clustered index determines the physical order of data (only one per table). Non-clustered indexes create separate structures pointing to the data. Don’t assume they’re the same.

Forgetting that indexes don’t help with all queries: Indexes are most useful for equality and range queries on indexed columns. Queries that scan most of the table won’t benefit from indexes.

• Site Home: Main landing page for computer-science notes.

• Practice: Practice problems for revision.

• Discrete Mathematics

• Algorithm Implementation