Indexing in DBMS: B+ Trees and Query Performance | Part 9

An index is an extra lookup structure that can help the database find rows without scanning the whole table. B-tree/B+ tree families are common; not every index is sorted or small.

This is Part 9 of the DBMS exam notes. These are general BTech CSE notes, not one university syllabus. Previous: Part 8: Crash Recovery. For index choices in a revision table see the Exam Numericals Hub, and for query practice see SQL output questions.

1. Why an index helps

Without a useful index, a table scan examines the table pages. With an appropriate index the planner can locate a smaller set of matching entries. The price is extra storage and extra maintenance work on writes that affect indexed entries, because the index must be kept in step.

2. Types of index

Type	Meaning	Note
Clustered organization	Rows are organized by one clustering key; details depend on the engine	One physical row ordering per table
Secondary (non-clustered)	Separate structure that points to rows	Many allowed
Dense	An entry for each search-key value or record, depending on duplicate handling	Bigger, finds any key directly
Sparse	Typically one entry per data block in the textbook model	Smaller, needs sorted data
Composite	Index on two or more columns	Order of columns matters (leftmost prefix)

3. Worked numbers: dense vs sparse index

A file has 100,000 records of 100 bytes each. Block size is 4096 bytes. An index entry (key + pointer) takes 20 bytes.

• Records per block = 4096 / 100 = 40 (rounded down). Data blocks = 100000 / 40 = 2,500.
• Binary search on the data file: log2(2500) rounded up = 12 block reads.
• Index entries per block = 4096 / 20 = 204.
• Dense index: 100000 / 204 = 491 blocks. Binary search 9 reads, plus 1 data read.
• Sparse index: 2500 / 204 = 13 blocks. Binary search 4 reads, plus 1 data read.

Result (program-checked): data file 12, dense index 9 + 1 = 10, sparse index 4 + 1 = 5 block reads. The sparse index has fewer pages in this simplified sorted-file model; this is a page-count calculation, not a measured speed claim.

4. B+ tree basics

• All search-key entries appear in the leaf level. Leaves are linked, so range queries (BETWEEN, >, <) just walk along the leaves.
• Internal nodes only guide the search.
• The tree is balanced: every leaf is at the same depth.
• In the textbook convention used here, order n means at most n child pointers in an internal node and n-1 keys. Non-root internal nodes have at least ceil(n/2) children; leaves have at least ceil((n-1)/2) keys. Leaf capacity is assumed separately below. Real storage layouts and other textbooks can use different order conventions.

Worked example: order and height

Pointer = 8 bytes, key = 4 bytes, block = 4096 bytes. The largest n with 8n + 4(n-1) <= 4096 is n = 341. So a node holds up to 340 keys. Minimum fill: 171 pointers in an internal node, 170 keys in a leaf.

How many levels are needed for 1,000,000 keys? With full nodes, 2 levels hold 340 x 341 = 115,940 keys, so you need 3 levels. For the maximum-height bound, a 3-level tree has a minimum of 2 x 171 x 170 = 58,140 keys, a 4-level tree a minimum of 2 x 171^2 x 170 = 9,941,940 keys, and a 5-level tree a minimum of 2 x 171^3 x 170 = 1,700,071,740 keys. Therefore 1,000,000 keys cannot fit a 4-level tree under these minimum-occupancy rules: the maximum is 3 levels. Do not confuse a minimum occupancy count with the capacity of a level.

Result: n = 341; exactly 3 levels for 1 million keys under these simplified capacities and minimum occupancies. An uncached root-to-leaf index traversal visits 3 pages; fetching a separate data page can add another read. This is not a measured query latency.

5. Equality and range queries

For WHERE id = 500, the tree goes root to leaf and finds one key. For WHERE id BETWEEN 500 AND 900, it finds 500, then reads along the linked leaves until it passes 900. A hash index is fast for equality but cannot do ranges.

6. When an index will not help

• The column has very few different values (for example a yes/no flag). Low selectivity means many rows match anyway.
• A function is applied on the column, such as WHERE UPPER(name) = 'RAM', unless a matching index exists.
• A composite B-tree index (a, b) is usually most effective for a-leading conditions. A query on b alone may still use the index, skip-scan or a full index scan depending on the engine, data and planner; it is not universally impossible.
• The table is tiny, so a scan is cheaper.

7. Common mistakes

• Saying a table can have many clustered indexes. It has one.
• Forgetting that indexes slow down writes.
• Mixing up dense and sparse: dense has an entry for every record.

8. Practice questions

Q1. A file has 20,000 records of 200 bytes, block 4000 bytes. How many data blocks?

Answer: 4000 / 200 = 20 records per block. 20000 / 20 = 1,000 blocks.

Q2. For the same file, a sparse index has one entry per block with 25-byte entries. How many index blocks?

Answer: 4000 / 25 = 160 entries per block. 1000 / 160 = 6.25, so 7 index blocks.

Q3. A composite index is on (city, age). Which query can use it fully: WHERE age = 20, or WHERE city = 'Pune' AND age = 20?

Answer: the second one. The first skips the leftmost column, so it does not get the same straightforward leading-key lookup; the planner may still find another useful index access path.

9. B+ tree search and range diagram

Root separator: 20
Keys <20 → Leaf A
Keys ≥20 → Leaf B
Leaf A: [5,10,15] → Leaf B: [20,25,30]
Equality 25: root → Leaf B → key 25
Range 10..25: root → Leaf A → follow link → Leaf B
Range result: 10,15,20,25

Separator 20 appears in the root and the leaf; internal separators guide navigation, while leaf entries identify data. This is a two-leaf teaching sketch, not the order 341 million-key tree. A range visits its starting path and the leaf pages needed for matching keys; it does not stop after one root-to-leaf path.

10. Height: minimum occupancy is not maximum capacity

The earlier example assumes internal fanout ≤341, leaf capacity 340, minimum non-root fanout 171 and minimum leaf occupancy 170. Headers, leaf record-pointer widths and duplicate storage are ignored. Real leaf capacity can differ from internal-node capacity.

from math import ceil, log2
records, record_bytes, block, entry = 100000, 100, 4096, 20
data_pages = ceil(records / (block // record_bytes))
index_per_page = block // entry
dense_pages = ceil(records / index_per_page)
sparse_pages = ceil(data_pages / index_per_page)
print("Pages:", data_pages, dense_pages, sparse_pages)
print("Binary-search model:", [ceil(log2(p)) for p in
                                (data_pages, dense_pages, sparse_pages)])
n = max(k for k in range(2, block) if 8*k + 4*(k-1) <= block)
leaf_max, leaf_min, child_min = n-1, ceil((n-1)/2), ceil(n/2)
for levels in (2, 3, 4):
    minimum = 2 * child_min**(levels-2) * leaf_min
    maximum = n**(levels-1) * leaf_max
    print(levels, "levels: min", minimum, "max", maximum)

Pages: 2500 491 13
Binary-search model: [12, 9, 4]
2 levels: min 340 max 115940
3 levels: min 58140 max 39535540
4 levels: min 9941940 max 13481619140

A million is larger than the maximum for 2 levels but smaller than the minimum for 4 levels. Therefore the permitted height is 3 levels in this exact model. The original 4-level worst-case claim mixed minimum occupancy with capacity and is corrected above. Cached root/internal pages can reduce physical reads; non-covering lookups may need data-page reads.

11. A real composite-index plan on SQLite

CREATE TABLE learner (id INTEGER PRIMARY KEY, city TEXT, age INTEGER);
INSERT INTO learner VALUES (1,'Pune',20),(2,'Pune',22),
                           (3,'Delhi',20),(4,'Pune',20);
CREATE INDEX idx_city_age ON learner(city,age);
SELECT id FROM learner
WHERE city='Pune' AND age=20 ORDER BY id;
EXPLAIN QUERY PLAN
SELECT id FROM learner WHERE city='Pune' AND age=20;

Actual result IDs: 1 and 4. The tested plan used SEARCH learner USING COVERING INDEX idx_city_age (city=? AND age=?). Exact EXPLAIN wording can vary by SQLite version; inspect your own plan. SQLite's INTEGER PRIMARY KEY aliases the rowid here, so the secondary index can supply the selected id without fetching the table row.

12. Index design decision table

Need	Check before adding an index
Equality or range	B-tree family supports both; hash indexes target equality
Composite filter	Match leading columns, query predicates and possible skip-scan behavior
Many matching rows	Compare scan and lookup costs, do not assume index is always faster
Selected columns in index	Check covering/index-only behavior for the engine
Frequent writes	Balance read benefit against index maintenance and space
Function predicate	Check matching expression index and engine support

13. Primary, clustered and sparse are not synonyms

A primary key is a uniqueness/identity constraint. A clustered organization is a physical storage choice. Some engines store primary-key data in a clustered index; others keep heap data and a separate unique index. PostgreSQL CLUSTER reorders a table once and does not maintain that order through every future update. The textbook primary/sparse index assumes a sorted data file; do not apply that label universally to every SQL PRIMARY KEY.

14. End-topic questions

1. Why are leaves linked? To traverse consecutive key ranges without restarting from the root for each key.
2. Is an index always smaller than its table? No; included values, many indexes and storage overhead can use substantial space.
3. Does a 3-page index path mean 3 total reads? Only for that uncached traversal model. Data pages, range leaf pages and caching change the total.
4. Can an index help a query on the second column alone? Sometimes; engine-specific skip-scan or index scans may be chosen. Leading-prefix access is generally more direct.
5. Does a low-cardinality field never benefit? No. Distribution, selectivity, partial indexes and the query matter.
6. What happens on leaf overflow? A split creates another leaf and updates parent separators; root splitting can add a level.
7. What does EXPLAIN establish? The chosen plan, not measured wall-clock speed. Use actual timing separately.

Verification: all original numericals, corrected height bounds, diagram range result, SQLite query and plan executed. No PostgreSQL benchmark claimed. Sources: Purdue B+ tree lecture, PostgreSQL multicolumn indexes, SQLite query planner and SQLite EXPLAIN QUERY PLAN and PostgreSQL CLUSTER.

15. Five-minute revision

• Index = faster reads, slower writes, extra space.
• Clustered: one per table. Dense: covers every search-key value/record in the stated model. Sparse: entry per block.
• B+ tree: balanced, data in linked leaves, good for ranges.
• Check selectivity before adding an index.

DBMS Exam Notes series: Previous: Part 8: Crash Recovery | DBMS series and hub