Storage: pages, B+ tree maths and hashing

Part of the free LogicWiz SQL & Databases course, Module 16: Inside the DBMS. The queries and practice run in the app on real Postgres.

IRCTC has crores of bookings, yet your PNR status loads in a blink. The table is far too big for memory. The secret is that a B+ tree finds one booking among a million in about four disk reads.

You'll learn to

  • Count records per block and blocks per file
  • Work out the order of a B+ tree node and the height of the tree
  • Explain when hashing beats a B+ tree and when it cannot help

Learn

Disks read pages, not rows

Tables live on disk in fixed-size blocks (Postgres calls them pages, 8 KB each). The disk always reads a whole block, so query cost is counted in block reads: everything in memory is far faster.

  • Blocking factor (records per block): bfr = ⌊B / R⌋ for block size B and record size R. Rows don't cross blocks, so we round down.
  • Blocks for the file: b = ⌈r / bfr⌉ for r records. We round up: a half-full last block is still a block.
  • A heap file is unsorted. Finding one row means a scan: b/2 reads on average, b in the worst case. A sorted file allows binary search: ⌈log₂ b⌉ reads.

Look at real pages

SHOW block_size;

CREATE TABLE t (id INT);
INSERT INTO t SELECT generate_series(1, 1000);

SELECT pg_relation_size('t') / 8192 AS pages;

SELECT id, ctid
FROM t
WHERE id IN (1, 226, 227, 1000);

ctid is a row's address: (page, slot). One INT row takes 36 bytes with its header and slot pointer, so 226 rows fill a page: row 227 starts page 1, and 1,000 rows need 5 pages.

The order of a B+ tree node

Each B+ tree node is one block.

Internal node: p child pointers and p − 1 keys must fit: p·P + (p − 1)·K ≤ B, so p = ⌊(B + K) / (K + P)⌋.

Leaf node: n pairs of (key, record pointer) plus one pointer to the next leaf: n·(K + Pr) + P ≤ B, so n = ⌊(B − P) / (K + Pr)⌋.

Example: B = 512, key K = 9, block pointer P = 6, record pointer Pr = 7.

  • p = ⌊521 / 15⌋ = 34. Check: 34·6 + 33·9 = 501 ≤ 512, but 35 pointers need 516.
  • n = ⌊506 / 16⌋ = 31. Check: 31·16 + 6 = 502 ≤ 512.

Let SQL do the arithmetic

-- B = 4096 bytes, key = 8, block pointer = 8, record pointer = 8
SELECT (4096 + 8) / (8 + 8) AS internal_order,
       (4096 - 8) / (8 + 8) AS leaf_capacity,
       4096 / 100 AS records_per_block_of_100_bytes;

Integer division in Postgres drops the fraction, which is exactly the ⌊ ⌋ (floor) these formulas need. For ⌈ ⌉ use CEIL(x / y::NUMERIC).

How tall is the tree?

Index 1,000,000 records with B = 4096 and 8-byte keys and pointers, so p = 256 and n = 255.

  1. Leaves: ⌈1,000,000 / 255⌉ = 3,922.
  2. The level above: ⌈3,922 / 256⌉ = 16 nodes.
  3. Above that: ⌈16 / 256⌉ = 1, the root.

So the tree has 3 levels. A lookup reads 3 index blocks plus 1 data block = 4 reads. A heap scan of the same rows (100-byte records, 40 per block, 25,000 blocks) needs 12,500 reads on average.

When every node is full, 3 levels hold up to 256 × 256 × 255 = 16,711,680 records.

Height with a recursive CTE

WITH RECURSIVE levels(level, nodes) AS (
  SELECT 1, CEIL(1000000 / 255.0)
  UNION ALL
  SELECT level + 1, CEIL(nodes / 256)
  FROM levels
  WHERE nodes > 1
)
SELECT * FROM levels;

Level 1 is the leaves; each step up divides by the fan-out and rounds up, until one node (the root) is left.

Hashing: straight to the bucket

A hash index runs the key through a function, such as h(k) = k mod 4, and goes straight to that bucket (block).

  • Keys 12, 17, 21, 30, 44 land in buckets 0, 1, 1, 2, 0. Two keys in one bucket is a collision; when a bucket is full, an overflow block is chained to it.
  • Static hashing has a fixed number of buckets, so chains grow long. Extendible hashing keeps a directory that doubles and splits only the full bucket.
  • An equality lookup costs about 1 read. But hashing scatters keys, so it is useless for ranges (BETWEEN, <) and for ORDER BY. That is why B+ trees are the default index.

The two classic slips: rounding the wrong way (blocking factor and node order round down, block and node counts round up), and forgetting the data block at the end of an index lookup (tree levels + 1). Integer division in SQL floors silently: 30001 / 40 is 750, but the file needs 751 blocks.

Read the question's definition first. Some books define the order as the maximum number of children (as here), others as the maximum number of keys, others as the minimum keys d (a node holds d to 2d keys). Height may count levels from 1 or from 0. Also asked: in a B+ tree all records sit in the leaves, which are linked for range scans; in a B tree, internal nodes hold records too, so it has fewer keys per node.

In one line

bfr = ⌊B/R⌋, blocks = ⌈r/bfr⌉; B+ tree order p = ⌊(B+K)/(K+P)⌋, leaf = ⌊(B−P)/(K+Pr)⌋; lookup = levels + 1 reads; hashing is for equality only.

Interview corner

Why do databases use B+ trees instead of binary search trees?

A binary tree node holds one key, so a million keys need about 20 levels, each a separate disk read. A B+ tree node is a whole disk block holding hundreds of keys, so the same million keys fit in 3 levels. Linked leaves also make range scans cheap.

B tree vs B+ tree?

In a B+ tree every record pointer lives in the leaves, internal nodes hold only keys for routing, and leaves are linked in order. In a B tree, internal nodes hold record pointers too, so each node fits fewer keys and range scans have to walk up and down the tree. Databases use B+ trees.

When would you choose a hash index?

When the only queries are exact matches on the key, like session id or PNR lookups: a hash goes straight to one bucket. It can't help ranges, prefixes or ORDER BY. In Postgres, a B+ tree (btree) handles equality almost as well, which is why it is the default.