E ExamMaster

CS Core & Software Engineering · Databases

Indexing and B+ Trees

Clustered versus secondary indexes and B+ trees that find a campus-shop sale without a full scan.

The kiosk has four sales. Finding Asha's two rows by scanning is fine; finding them among a million is not. An index is a side structure — usually a B+ tree — that turns "student_id = 1" into a few page reads. This lesson stays on those four ids so the shapes stay visible.

  • CS Core & Software Engineering
  • Hard level
  • 6 concepts
  • 5 practice questions

1Primary versus secondary index

An index is a side structure that answers "where is the row with this key?" without walking every Sale row. A primary (clustered) index is on the order the rows are stored. If Sale is stored in sale_id order, the primary index is on sale_id — and a table can have only one such order, so only one clustered index.

A secondary (non-clustered) index is on some other column, student_id say, and stores pointers to the rows. Finding Asha's sales without that index means scanning all four rows. With it, student_id 1 points at sale 100 and sale 102. We can have many secondary indexes; each is extra storage and extra work on every insert.

Figure. The file is in sale_id order (one clustered index). A secondary index on student_id points at Asha's two sales.

Find Asha without and with an index

  1. No indexRead sale 100, 101, 102, 103 — keep the two with student_id 1.
  2. Secondary on student_idLook up 1 → {100, 102}; fetch those two rows.
  3. Clustered on sale_idThe file itself is in sale_id order; one clustered index only.
Two indexes on Sale
IndexKeyHow many per table
Primary / clusteredsale_id (file order)at most one
Secondarystudent_idas many as we build
The key difference between a clustered and a non-clustered index is
  1. A clustered index can only be created on primary keys
  2. A clustered index determines the physical order of rows, so a table can have only one
  3. A non-clustered index physically reorders the table

Clustered = the file order (one). Secondary = a separate pointer structure (many).

2Dense versus sparse index

A dense index has one entry per record: four Sale rows, four index entries. A sparse index has one entry per block (or other storage chunk) and needs the file to be ordered on that key, so you land on a block and scan inside it. Sparse is smaller; it cannot sit on an unordered secondary key.

On four rows the difference is tiny. The idea scales: a million sales in 1000-row blocks need a million dense entries or about a thousand sparse ones on the clustered sale_id. Secondary indexes are dense — each student_id value needs its own pointer list, and the file is not in student_id order.

Figure. Four rows, two per block: dense keeps four entries, sparse keeps two.

Count entries on Sale

  1. Dense on sale_id4 entries — one per row.
  2. Sparse, 2 rows/block2 entries — one per block, file must be sale_id-ordered.
  3. Secondary on student_idDense: 1, 2, 3 each have a pointer list.

Entries for four sales

Sale has 4 rows, 2 rows per block, clustered on sale_id. How many entries in a dense sale_id index versus a sparse one?

  • rows4
  • blocks = 4 / 22
  • dense entries4
  • sparse entries2

Pro tip. Sparse needs the file ordered on that key. A student_id index cannot be sparse on a sale_id-ordered file.

A sparse index needs the file to be
  1. Hashed
  2. Ordered on the index key, with one entry per block
  3. Unsorted, so each row has its own entry

Sparse lands on a block and scans. That only works if the block is a slice of the ordered key.

3B-tree: keys in every node

A B-tree is a balanced search tree whose nodes are disk pages. Every node — root, internal, leaf — stores keys and can store record pointers. Finding sale 102 means comparing 102 to the keys in the root, descending to one child, repeating until you hit the key. The tree stays balanced, so every sale is the same number of page reads from the root.

That "keys everywhere" design is the contrast the next concept needs. Range queries (sale_id between 101 and 103) may have to visit several leaves that are not linked to each other, climbing back up to find the next sibling. B+ trees fix that by moving all the record pointers to a linked leaf level.

Figure. A B-tree may store sale 102 in an internal node, not only in a leaf.

Find sale 102

  1. RootCompare 102 to the separator keys; pick a child page.
  2. DescendRepeat in that page until 102 is found (any level may hold it).
  3. BalanceEvery sale is the same depth — no long skinny path for 103.
In a B-tree (not B+), record pointers may sit
  1. Only in the root
  2. In internal nodes as well as leaves
  3. Only in a separate hash file

B-tree nodes at every level may hold keys and pointers. B+ trees move the record pointers to the leaves.

4B+ tree: all rows in linked leaves

A B+ tree keeps every record pointer in the leaves. Internal nodes hold only separator keys and child pointers — they are a directory, not a warehouse. The leaves are linked left-to-right in key order. After you find sale 101, "the next sale" is the next leaf entry, not another root-to-leaf walk.

That is why range queries and ORDER BY sale_id use B+ trees. Hash indexes answer "exactly sale 101" quickly and cannot walk 101–103. The four kiosk sales in a tiny B+ tree sit in one leaf chain: 100, 101, 102, 103. Internal separators just decide which leaf to open first.

Figure. Internal node is only a directory. The four sale keys live in a linked leaf chain.

Range 101 to 103

  1. DescendUse internal separators to open the leaf that holds 101.
  2. WalkFollow leaf next-pointers: 101, 102, 103.
  3. StopNext key is past 103, or the chain ends.
B-tree versus B+
PieceB-treeB+ tree
Record pointersany levelleaves only
Leaf linksusually noyes, for ranges
Internal nodeskeys + pointersseparators only
Why do B+ leaves store sibling pointers in key order?
  1. To support range scans without climbing back to internal nodes for every next key
  2. To make hash equality faster than a hash index
  3. To allow several clustered indexes

Once the first leaf of the range is found, the chain walks the rest. That is the range-query reason B+ trees exist.

5Order and fanout

The order of a B+ tree is a capacity: how many keys (and children) a node may hold. Fanout is how many children an internal node actually points at. High fanout means a short tree — a few page reads from root to Asha's sale — because each page branches wide.

On four keys the tree is one leaf and maybe a tiny root; fanout barely matters. On a million sales, a fanout of 100 makes height about 3 (100³ = 1,000,000). That is the whole point of putting many keys in one disk page instead of using a binary tree of height 20.

Figure. A million keys. Wide nodes make a short tree; a binary tree is twenty page reads deep.

Height from fanout

  1. KeysAbout 1,000,000 sales.
  2. Fanout 100100³ = 1,000,000 — height about 3.
  3. Binary2²⁰ is a million — height about 20 page reads.

Fanout versus height

A million keys. About how many levels with fanout 100 versus fanout 2?

  • 100^31,000,000
  • height at fanout 100about 3
  • 2^201,048,576
  • height at fanout 2about 20

Pro tip. Wide pages (high fanout) are why B+ trees beat binary trees on disk.

Raising fanout, for the same number of sales, does what to height?
  1. Increases it — more keys per node means a taller tree
  2. Decreases it — each level covers more keys
  3. Leaves it unchanged — height depends only on sale_id

Height is roughly log_fanout(N). Bigger fanout, smaller log.

6Height and I/O cost

Each edge you follow in a B+ tree is a disk page read — an I/O. A point lookup ("sale 102") costs about the height plus the final row fetch if the leaf stores a pointer rather than the row. A range walk adds one I/O per extra leaf page, not one I/O per key, because a leaf holds many keys.

On the four-sale kiosk the height is 1 and the cost is two page reads if the root and the leaf are different pages — or one if they fit together. The formula is what you take to a larger file: I/Os ≈ height + leaf pages in the range. That is why we care about fanout: it is the cheapest way to cut height.

Figure. Point lookup of sale 102: one I/O per level, plus a row fetch when the leaf stores a pointer.

Cost of "sale 102"

  1. Height hh page reads root → leaf.
  2. Row fetch+1 if the leaf holds a pointer, not the row.
  3. Range 101–103h to the first leaf, then +1 per extra leaf page.

Four keys, height 1

A tiny B+ tree of the four sale_ids has height 1 (root + one leaf). Point lookup of 102, leaf stores a pointer. How many I/Os?

  • height1
  • root → leaf1 I/O + 1 I/O
  • row fetch+1
  • total I/Os3

Pro tip. If the leaf stored the row itself, drop the last fetch: 2 I/Os.

For a point lookup, I/O cost scales mainly with
  1. The number of columns in Sale
  2. The height of the B+ tree (fanout-controlled)
  3. The number of secondary indexes on other tables

Each level is a page read. Fanout cuts height; that is the I/O win.

Notes

  • A primary/clustered index is on the ordering key (one per table); a secondary index is on a non-ordering field and is always dense.
  • Dense index has one entry per record; sparse index has one entry per block, so it is smaller but needs the file to be ordered.
  • In a B-tree, keys and data pointers appear in all nodes; in a B+ tree, all data pointers are in leaves and internal nodes hold only keys.
  • B+ tree leaves are linked in a sorted list, making range queries efficient; this is why databases prefer B+ trees.
  • A B+ tree of order n has each internal node holding up to n-1 keys and n children; the tree stays balanced with height O(\log n).

Formulas

  • B+ tree of order p: internal node has at most p children and p-1 keys, at least ceil(p/2) children.
  • Search/insert/delete cost in a B/B+ tree = O(\log_p N) where p is the order and N the number of keys.
  • Order (fan-out) p from block size B and pointer/key sizes: p \times ptr + (p-1) \times key \le B.
  • Number of block accesses for a search \approx height of the tree + 1 (for the data block).
  • Dense index entries = number of records; sparse index entries = number of blocks.

Exam traps & shortcuts

  • B+ tree: 'data only in leaves, leaves linked' — that's why range scans are fast.
  • Higher order (fan-out) means shorter tree height and fewer disk accesses.
  • A table can have only one clustered/primary index but many secondary indexes.

Reference tables

How we find Asha
MethodWork on 4 rows / on 10^6
Scan Sale4 comparisons / a million
Secondary on student_idlookup 1 → {100, 102}
B+ range on sale_iddescend, then walk the leaf chain

Recap

One file order, a pointer file, a short wide tree.

Clustered
File order; one per table. Sale in sale_id order.
Secondary
Pointer file; many allowed. student_id → {100, 102}.
Dense / sparse
Per record vs per block. Secondary is dense.
B+
Record pointers in linked leaves. Ranges walk the chain.
I/O
Point lookup ≈ height (+ row fetch). Fanout cuts height.

Practise Indexing and B+ Trees

Reading is free and needs no account. Practice, mocks and progress live in the app.

  • 5 exam-style questions on this topic, with explanations
  • A 3-question practice set that ends the chapter
  • Timed mocks scored with the real marking scheme
  • Readiness tracked per topic, kept on your device
Continue with Google — freeNo card, no trial. Works offline once installed.