Handbooks / DBMS / Chapter 2

Indexing and Storage

6 pages · ~4 min✓ Reviewed

Builds on ER Model and Normalization. Next up: Transactions and ACID.

DBMSPage 1

Pages and Records: Storage Basics

1. Pages and Records

  • Page = fixed-size disk block, the smallest unit the DB reads or writes
  • Often 4-16 KB: 8 KB PostgreSQL, 16 KB InnoDB
  • One row lookup reads the whole page
  • Record lives in a slot; slot directory maps slot number to byte offset
  • Record ID = (page number, slot number)
  1. Record ID(page 7, slot 2)
  2. Page 7one disk read
  3. Slot directoryslot 2 → offset
  4. Recordbytes at offset

2. Heap Files and Record Layout

  • Heap file = pages in no particular order
  • No index means a full scan of every page
Fixed-lengthVariable-length (VARCHAR)
Find fieldsimple offset calculationneeds the slot directory
Too big?nocan overflow into extra pages

3. Cost Model

  • Speed is measured in page I/Os, not rows
  • Fewer pages touched = faster query
  • Heap scan of 1,000 pages = 1,000 I/Os, even for one row
Count pages, not rows

A 1-row lookup still costs a whole page read. Without an index, it costs every page.

DBMSPage 2

Primary vs Secondary and Clustered vs Non-Clustered

1. Primary vs Secondary

  • Primary index: built on the primary key, unique and not null
  • Secondary index: built on any other column, can be non-unique

2. Clustered vs Non-Clustered

ClusteredNon-clustered
Leaf holdsthe full row, in key orderkey + pointer to the row
Pointernone, row is in the leafheap: record ID; InnoDB: primary key
Per tableonly onemany
Range scanadjacent pages, sequentialrandom row fetches
  1. Secondary indexfind the key
  2. Primary keyread from leaf
  3. Clustered indexsecond traversal
  4. Rowfound

3. Range Scans

  • Clustered range: read adjacent pages in order
  • Non-clustered range: one random fetch per matching row
InnoDB secondary lookup

It costs two traversals: secondary index to get the primary key, then the clustered index to get the row.

DBMSPage 3

B+ Trees: The Default Index Structure

1. Shape of a B+ Tree

  • Internal nodes hold keys + child pointers only
  • Leaves hold all the data or row pointers
  • Leaves form a doubly linked list: find start key, walk sideways for a range
  • Node = one page, fan-out in the hundreds: millions of rows, only 3-4 levels

2. Lookup Cost and Splits

  • Lookup = O(log_f N) page reads, f = fan-out
  • 3 levels = 3 page I/Os, root usually cached
Insert into a full leaf
  1. 1Leaf full
  2. 2Split in twotwo half-full leaves
  3. 3Push separator upparent gains a key
  4. 4Cascade to roottree stays balanced

3. Composite Index (a,b,c)

sql
CREATE INDEX idx_abc ON t (a, b, c);

leftmost-prefix rule

FilterUses idx_abc?
ayes
a + byes
a + b + cyes
b aloneno
Leftmost prefix

Skip a and the index cannot help. Put the column you always filter on first.

DBMSPage 4

Hash Indexes vs B+ Trees

1. Hash Index

  • Hash function on the key picks a bucket
  • Equality WHERE id = 5: O(1) average
  • No range, ORDER BY or prefix: hashing destroys key order
  • Collisions: chaining in bucket or overflow pages
  • Too many collisions: lookups slide toward O(n)

2. Hash vs B+ Tree

HashB+ tree
=O(1), fasterO(log N)
< > BETWEENnoyes
ORDER BYnoyes
LIKE 'abc%'noyes

3. In Practice

sql
CREATE INDEX idx_id ON t USING hash (id);

PostgreSQL

  • MySQL InnoDB: adaptive hash index, built automatically in memory
  • PostgreSQL: USING hash; B+ tree is the default in both

4. Interview Point

  • Why can't a hash index do BETWEEN? Hashing destroys key order, so neighbours are not adjacent
  • When pick hash over B+ tree? Equality-only lookups; it is faster for =
  • Why can a hash index slow down? Heavy collisions push lookups toward O(n)
Remember

Equality only: hash. Range or sort: B+ tree.

DBMSPage 5

Index Maintenance Cost, Mistakes and Cheat Sheet

1. What a write costs

StatementTableIndexes touched
INSERT / DELETEwrittenevery index
UPDATE indexed columnwrittenthat index: entry moves
UPDATE unindexed columnwrittennone
  • 5 indexes = about 6 structures written per row

2. Common mistakes

  • Index on every column: slower writes, wasted memory and disk, planner may pick wrong
  • Low cardinality (boolean, gender): planner prefers a full scan anyway
  • UUIDv4 clustered key: random inserts cause page splits and fragmentation
  • Sequential keys just append to the last page
Index only what you use

Columns in WHERE, JOIN and ORDER BY only.

3. Cheat sheet

SituationPick
Equality onlyhash
Range or sortB+ tree
Clustered indexone per table
Composite indexleftmost prefix
Read-heavy tablemore indexes
Write-heavy tablefewer indexes
DBMSPage 6

Check yourself

An index on (a, b, c) exists. Does WHERE b = 5 AND c = 2 use it for a seek?
  • No: the leftmost-prefix rule needs a first.
  • Without a, the sorted order doesn't help.
  • Expect a scan.
InnoDB, secondary index on email. How many tree traversals does SELECT * WHERE email = 'x' take?
  • Two.
  • Secondary index gives the primary key.
  • Clustered index then gives the row.
Inserts slow down after switching the clustered key from an auto-increment id to UUIDv4. Why?
  • Random keys land in random pages.
  • Full pages split, causing fragmentation.
  • Sequential keys just append to the last page.
A hash index exists on id. Is WHERE id BETWEEN 5 AND 9 fast?
  • No: hashing destroys key order.
  • Hash serves only =.
  • Use a B+ tree and walk the linked leaves.