How databases delete, build, and choose the right index

1 Deletion & merges — underflow, borrowing, and shrinking

Recall from Session 6 that a B+ tree of order (also called the fan-out) n has these rules: every node holds at most n−1 keys, and every node except the root must stay at least half full. Inserting could make a node too full, so we split. Deleting can make a node too empty — a condition called underflow — and the cures are the mirror image of a split: borrow (also called redistribution) or merge (also called coalescing).

The minimum-occupancy rule

The whole reason a B+ tree gives us guaranteed O(log n) lookups is that it stays balanced and reasonably full. If we let nodes drain to almost empty, the tree would get tall and wasteful. So the structure enforces a floor:

When a deletion drops a node below its floor, we have underflow and must fix it before we finish.

The deletion algorithm, step by step

Two important details that beginners trip over:

• In a B+ tree, all real data lives in the leaves. Internal nodes only hold copies of keys used as signposts. So a deleted key might still appear in an internal node as a separator — and that's fine; it's just a routing label, not a missing/duplicate row.
• After a borrow or merge, the parent's separator key may need updating, and a merge removes a key from the parent — which can make the parent underflow too. So fixes can cascade upward, exactly the way splits cascade upward during insertion.

Borrowing (redistribution)

If an underflowing node has an adjacent sibling with keys to spare (i.e. the sibling is more than half full), we move one key across and patch the parent's separator. This is cheap and local — no nodes are deleted.

Merging (coalescing)

If neither sibling can spare a key (both are exactly at the floor), borrowing would just push the problem to the sibling. Instead we merge the underflowing node with a sibling into one node. Because two half-full nodes combine to at most one full node, this is always legal. Merging two children means the parent loses one child and one separator key — which is why the parent can underflow and the fix may climb the tree.

          root:        [ 13 | 25 ]
                     /     |      \
   leaf A:[5, 9]  leaf B:[13,17]  leaf C:[25,30,33]
       (chained:  A <-> B <-> C)

          root:        [ 13 | 30 ]   ← separator updated 25→30
                     /     |      \
   leaf A:[5, 9]  leaf B:[13,25]  leaf C:[30,33]

          root:        [ 13 ]          ← lost separator 25
                     /      \
        leaf A:[5,9]   leaf BC:[13,25,30]

When the height actually shrinks

Splits during insertion grow the tree taller only in one special case: when the root itself splits. Deletion shrinks the tree in the mirror case: when a merge propagates all the way up and the root ends up with no keys left (only a single child pointer). Then we discard the old root and promote its only child to be the new root — the tree loses one level.

2 Bulk loading — building a B+ tree the fast way

If you already have a big pile of data (say you're creating an index on an existing table, or loading millions of rows), you could just call insert once per key. But each insert from Session 6 walks from the root to a leaf and may trigger splits — that's O(log n) work and lots of random page touches, per key. Bulk loading (also called bulk insertion or bottom-up construction) builds the tree far faster.

The algorithm

The key idea is bottom-up: instead of growing the tree top-down one insert at a time, you lay down the entire bottom row of leaves first (each filled to a chosen capacity), then build each higher level by taking the smallest key of each child as a separator in its parent. You repeat until a single node — the root — remains.

  L1:[2,3]  L2:[5,7]  L3:[11,13]  L4:[17,19]  L5:[23,29]
     (chained: L1 <-> L2 <-> L3 <-> L4 <-> L5)

  root: [ 5 | 11 | 17 | 23 ]
         /    |    |    |    \
       L1    L2   L3   L4    L5

Why bulk loading is faster

3 Composite & covering indexes

So far our index keys were a single column. A composite index (also called a compound or multi-column index) uses several columns combined into one key. The B+ tree sorts rows by the first column, then breaks ties with the second, then the third, and so on — exactly the phone-book ordering. This is also called lexicographic (dictionary) order.

Column order matters — a lot

Consider an index on (last_name, first_name). Because the tree is sorted by last_name first, here is what it can and can't accelerate:

  -- Index option A: city first, then age
  CREATE INDEX idx_city_age ON users (city, age);

  -- Index option B: age first, then city
  CREATE INDEX idx_age_city ON users (age, city);

  -- The query:
  SELECT * FROM users
  WHERE city = 'Delhi' AND age > 30;

Covering indexes — answering a query from the index alone

Normally an index entry gets you to the right location, and then the database does an extra step: it follows the pointer to the actual table row to fetch the other columns you asked for. That extra hop is the slow part for big result sets. A covering index contains every column the query needs — both the columns it filters on and the columns it returns — so the database can answer the query entirely from the index, never touching the table. This is called an index-only scan.

  SELECT email
  FROM users
  WHERE city = 'Delhi';

  -- email is part of the sorted key here
  CREATE INDEX idx_city_email ON users (city, email);

  -- PostgreSQL: keep email as a non-key "payload" via INCLUDE
  CREATE INDEX idx_city_inc ON users (city) INCLUDE (email);

4 Hash indexes vs B+ trees

A hash index is built on a hash function: a little formula that turns a key (like user_id = 8421) into a bucket number — a slot where the matching entry is stored. To look up a key, you hash it, jump straight to that bucket, and scan the (usually tiny) bucket. No tree to descend.

Static hashing — and why it's not enough

The simplest scheme, static hashing, fixes the number of buckets up front: bucket = hash(key) mod N. That's fine until the table grows. When buckets fill up, new entries spill into overflow chains (extra linked pages hanging off a bucket), and lookups degrade from O(1) toward O(chain length). Sizing too big wastes space; too small causes overflows. We need a scheme that grows gracefully.

Extendible hashing

Extendible hashing uses a directory that points to buckets, and looks at the first d bits of the hash (d is the global depth). When one bucket overflows, only that bucket is split (and the directory doubles only if needed), so the structure grows one bucket at a time rather than rehashing everything. Lookups stay close to a single bucket access.

Linear hashing

Linear hashing grows the table one bucket at a time in a fixed round-robin order, with no directory at all. A "split pointer" marches across the buckets; whenever the table gets too full overall, the next bucket in line is split. It avoids the directory entirely and spreads the cost of growth smoothly, which is why several real systems use it.

  bucket = key mod 4
  5  mod 4 = 1   → bucket 1
  9  mod 4 = 1   → bucket 1
  13 mod 4 = 1   → bucket 1   (bucket 1 now: [5, 9, 13])
  7  mod 4 = 3   → bucket 3

  Buckets:  0:[ ]   1:[5,9,13]   2:[ ]   3:[7]

The comparison table — when to use which

★ Putting it all together

You've now seen the full life of an index — building it, shrinking it, shaping it for multiple columns, and choosing a completely different structure when the workload calls for it. Here's the one-paragraph story tying today's four topics together:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• DBMS Session 7 — Index Structures 2 (your course handout for this session).

Papers, docs & deep dives

• CMU 15-445 Database Systems — tree & hash index lectures — Andy Pavlo's free course; the B+ tree and hashing lectures cover deletion, bulk loading, and extendible/linear hashing with excellent slides and videos.
• PostgreSQL Documentation — Index Types — the official rundown of B-tree vs hash (and GIN/GiST/BRIN), with exactly when each is appropriate; pairs directly with Topics 3 and 4.
• Silberschatz, Korth & Sudarshan — Database System Concepts (the "Indexing" & hashing chapters) — the standard textbook treatment of B+ tree deletion, bulk loading, and static/dynamic hashing with full worked examples.
• Markus Winand — Use The Index, Luke! — a famously clear, practical guide to composite indexes, the leftmost-prefix rule, and covering/index-only scans across real SQL databases.
• PostgreSQL — CREATE INDEX reference — documents INCLUDE (covering indexes), fillfactor (packing), and USING hash, the exact features used in this session's examples.