Physical Storage & Access Structures

01 · Foundation

Why we count blocks

Databases live on disk, and disk is slow in a way that dwarfs every other cost in the system. That single fact reduces performance analysis to counting block transfers.

Data must be in main memory to be used, so every access moves data between two levels:

• a block is the unit of storage in secondary memory;
• a page is the unit of storage in main memory.

Throughout this course we assume one page holds exactly one block — real systems may pack several blocks per page, but the assumption costs nothing and simplifies every formula. An I/O operation moves one block in either direction.

For a mechanical disk the time breaks down as:

Add them and a single block access costs roughly 10 ms, against roughly 1 µs for main memory: the cost of an access to secondary memory is about four orders of magnitude higher. In an I/O-bound application — which a DBMS overwhelmingly is — everything else disappears into the noise. Hence the definition this whole course runs on:

No constants, no units, no CPU term. When chapter 4 asks you to “estimate the cost”, it is asking for that count.

02 · Foundation

Blocks, tuples, and the block factor

Blocks are the physical unit; tuples are the logical one. The ratio between them is the first number you compute in every exercise.

A block’s size is fixed by the file system and disk formatting. A tuple’s size depends on the schema and is often variable — nullable columns, varchar, and other non-fixed types see to that. Inside a block sit the useful data, a page dictionary of offsets to each item (data and dictionary grow as stacks from opposite ends), header and trailer for the access method and the file system, and a checksum.

The number that matters is the block factor — how many tuples fit in one block:

with $S_B$ the block size and $S_T$ the average tuple size. The leftover space is either wasted (unspanned records) or used by letting a tuple straddle two blocks (spanned, or hung-up, records).

A worked instance you will see again and again — it is the running example of the whole deck:

Block size          8 KB = 8192 bytes
STUDENT tuple       95 bytes  (4+25+25+25+12+3+1)
  block factor      8192 / 95   = 86.2  →  87 tuples/block (slides round up)
  150 000 tuples    150000 / 87 = 1.7 K blocks
EXAM tuple          17 bytes
  block factor      8192 / 17   = 482 tuples/block
  1 800 000 tuples              = 5.3 K blocks

Every table is stored in exactly one primary physical structure, which holds all its tuples, and may have any number of secondary structures — indexes, which hold only some field values interleaved with pointers to the primary structure’s blocks. Three families exist, and they are not equally suited to the two roles:

03 · Structures

Sequential structures

Tuples laid out one after another. Two variants, distinguished only by whether that order means anything.

Three standard techniques keep an ordered structure from having to reorder globally: differential files with periodic merging (the paper Yellow Pages model), free space left in each block at load time so reordering stays local, and an overflow file whose blocks are chained to the ones that filled up — a principle that recurs in hash structures.

The practical conclusion from the lectures is worth internalising: entry-sequenced is the most common primary organization — but paired with secondary access structures. The heap holds the data; indexes make it findable.

04 · Structures

Hash structures and overflow chains

Associative access: given a key value, compute where it lives. Constant cost for equality — and no help whatsoever for ranges.

A hash structure has $N_B$ buckets, each typically one block. A hash function maps a key to a value in $[0, N_B - 1]$, in two stages: folding turns the key (a string, say) into a positive integer spread over a large range, then hashing reduces it modulo the bucket count.

Efficient for tables that are small and near-static, and for point queries — equality on the key. Inefficient for range queries, full-table queries, and very dynamic content.

When a bucket fills, the surplus goes into an overflow chain, and lookups must follow it. The expected extra cost is a function of two quantities: the block factor $B$, and the load factor

with $T$ the number of tuples. The lectures give the table from real access statistics — the average number of accesses to the overflow chain:

Typical designs sit between 50 % and 80 % occupancy. At $B = 3$ and 70 % load, a lookup costs $1 + 0.286$ I/O — one for the bucket, a fraction for the chain.

You do not need to memorise the table. Exercises always give you the overflow cost — “with a cost of access due to overflow of 1.3”, “filling factor below 50 %, no overflow cost” — and you add it to the 1 for the bucket itself.

05 · Indexes

The index taxonomy

An index is a structure of [search key, block pointer] records — the analytic index at the back of a book, in database form.

Two orthogonal distinctions produce the vocabulary. First, density:

• A dense index has an entry for every search-key value in the file. Only a search of the index plus one access to the tuple is needed. It works on entry-sequenced data.
• A sparse index has entries for only some values — typically one per block. It takes less space but is slower, and it requires the data to be sequentially ordered on the search key, because reaching the right block is only useful if scanning forward from it finds the tuple.

Second, the relationship between the search key (SK) and the ordering key (OK) of the primary structure:

A secondary index must be dense because tuples with adjacent key values may sit in entirely different blocks — there is nothing to scan forward through. A clustering index generalises the primary index to a non-unique ordering key: the pointer for value X leads to the block holding the first tuple with that key, and the rest follow contiguously.

Indexes are not free. They are smaller than the primary structure and often fit in memory, and they turn scans into lookups — but every insert, update and delete must also maintain every index. The lectures’ selection guidelines follow directly: do not index small tables; do index a primary key not already the key of the primary organization, heavily-used secondary keys, and frequently-accessed foreign keys; do index columns used in selections, joins, ORDER BY, GROUP BY, UNION, DISTINCT; but avoid indexing frequently-updated columns, columns a query will read a large proportion of anyway, and long character strings.

06 · Indexes

B+ trees

The structure SQL indexes are actually built from. Balanced — every root-to-leaf path has the same length — and shaped so that one node is one block.

A B+ tree is a multi-level index: a root, several intermediate levels, and the leaves. Its defining property is that all key values live in the leaves; internal nodes exist only to route.

• Each node holds up to $N-1$ search keys and $N$ pointers, sized so the node fills one block. The fan-out therefore depends on block size, key size and pointer size — and is large, so most blocks in the tree are leaves.
• A leaf holds at least $\lceil (N-1)/2 \rceil$ keys; an internal node keeps at least $\lceil N/2 \rceil$ pointers, so every node is at least half full.
• Keys within a node are sorted, and the leaves are chained left to right, which is what makes interval queries efficient.
• The set of leaves forms a dense index — every existing key value appears.

Lookup for value $V$ descends from the root; at each internal node, take $P_1$ if $V < K_1$, take $P_N$ if $V \ge K_{N-1}$, and otherwise take $P_{j+1}$ where $K_j \le V < K_{j+1}$.

The costs — the reason we are here:

That last row is the one students miss and examiners reward. If every attribute the query needs is already in the index, the data blocks are never touched. The lectures’ own example: SELECT ID FROM Student WHERE ID BETWEEN 6 AND 19 costs 2 intermediate levels + 3 leaves = 5 I/O, against 8 for the same range when the full tuples are wanted.

07 · Indexes

Composite indexes and the leftmost prefix

An index may be built on several attributes at once. Which queries it then serves is decided by one rule, and recent exams lean on it hard.

A B+ tree on (LastName, FirstName, City) orders entries lexicographically by that tuple. The consequence is the leftmost prefix rule: the index supports a predicate only if the predicates form a prefix of the index’s attribute list, with at most the last used attribute being a range.

Given B+ on (LastName, FirstName, City):

The third row is the trap. An index whose leading attribute is absent from the WHERE clause is not a cheap index — it is an irrelevant one, and the correct answer is to compare its cost against simply scanning the primary structure.

The estimator below is that exercise, made runnable: the three candidate indexes over Booking, the same WHERE clause, and the two numbers you owe for each — index blocks read and candidate pointers followed. The walk colours every attribute as the index reads it, so you can see why the date-first index reads a wide band of leaves yet follows few pointers, and the prefix-matched one wins on both. Reproduce all three, then open the real question.

08 · Costs

Lookup cost, structure by structure

This is the table the exam expects you to reproduce from understanding, not memory. Everything is “1 for the block you land on, plus whatever chasing you then have to do”.

For a primary structure — the one holding the actual tuples:

For a secondary structure — pairs of (K, pointer) over any primary structure:

“Follow a pointer” means load that block into memory — one I/O each.

A worked pair from the running example, to see the shapes:

SELECT * FROM STUDENT WHERE LastName = 'Rossi'      -- secondary B+ on LastName
  val(LastName) = 75 K over 150 K tuples            → 2 tuples per surname
  4 levels (3 intermediate + 1 leaf), 2 tuples fit in 1 leaf block
  cost = 3 + 1 + 2 = 6 I/O

SELECT * FROM EXAM WHERE Date = '10/6/2019'         -- secondary B+ on Date
  val(Date) = 500 over 1.8 M tuples                 → 3 600 tuples per date
  1.8 M pointers over 2 K leaves                    → 900 pointers/leaf → 4 leaves
  cost = 3 + 4 + 3 600 ≈ 3.6 K I/O                  ← the pointers dominate

Same structure, same tree height — and a thousandfold difference in cost, entirely because of selectivity. That is the intuition chapter 4 formalises.

Both of those cases are loaded in the calculator below, along with the rest of the tables above. Run them, check the numbers against the worked pair you just read, then start changing one thing at a time: ask a hash structure for a range and watch the plan collapse to a scan, or push val(A) down on the LastName index until the pointers overtake the table’s own block count. The formula it prints is the one an exam wants written out — every term named, every number justified.

Finally, two rules for combining predicates. In a conjunction, the DBMS picks the most selective supported predicate for the access and evaluates the rest in memory on the retrieved tuples. In a disjunction, indexes help only if every predicate is supported — then results are unioned and duplicates removed; if even one is unsupported, the whole query falls back to a full scan.