Lesson 25: Indexing¶
Single-level, multi-level and B+-tree index structures
About this lesson
Course: Database Management Systems
Unit 6: Data Storage and Indexes · 4 Lecture Hours
Lesson duration: 1 lecture
Reading: Elmasri & Navathe, Ch. 17
Learning Outcomes
- Explain the need for indexes and the cost they impose.
- Distinguish primary, clustering and secondary indexes.
- Distinguish dense from sparse indexes and say which must be which.
- Compute the size and search cost of a single-level and a multi-level index.
- Describe the structure and advantages of a B+-tree.
25.1 The Need for Indexes¶
Lesson 1 ended with the decisive limitation: a file can be physically organised on only one field. A STUDENT file sorted on Rollno gives no help whatever to WHERE Name = 'Ankit Sharma', which still costs a linear scan.
Index
An index is an auxiliary access structure on a file, used to speed up the retrieval of records that satisfy a condition on an indexed field. It is stored separately from the data file, and the data file itself is unchanged.
An index entry is a pair <field value, pointer>, where the pointer is a block address or a record address.
Because an index is smaller than the data file — it holds only one field and a pointer, not whole records — searching it costs far fewer block accesses.
The idea is exactly that of a book index: rather than reading every page to find "normalisation", you consult a short alphabetical list at the back and go straight to page 214.
A file may have any number of indexes, on any number of fields. That is how a single physical arrangement can serve many different queries.
Indexes are not free
- Storage. Each index consumes space, sometimes a substantial fraction of the table.
- Write cost. Every
INSERT,UPDATEandDELETEmust update every index on the table. A table with eight indexes has slow writes. - Maintenance. Indexes fragment and need periodic rebuilding.
So indexes trade write speed and space for read speed. Index the columns that are actually queried, and no others.
25.2 Types of Single-Level Ordered Index¶
An index file is itself a sorted file of <value, pointer> entries. Three kinds, distinguished by the field they are built on.
The three types
Primary index — built on the ordering key field of a sorted data file. That is, the field is both the physical ordering field and a key (unique). → Sparse: one entry per block, holding that block's anchor record (its first record).
Clustering index — built on the ordering field of a sorted data file where the field is not a key (values repeat). → Sparse: one entry per distinct value, pointing at the first block containing it.
Secondary index — built on a non-ordering field, key or not. The data file may be sorted on something else, or be a heap. → Dense: one entry per record (or per distinct value, with a level of indirection).
The decision tree
Is the index field the field the FILE IS SORTED ON?
| |
YES NO
| |
Is it unique (a key)? SECONDARY index
| | (must be DENSE)
YES NO
| |
PRIMARY CLUSTERING
(sparse) (sparse)
A file can have AT MOST ONE primary or clustering index
(it is sorted on only one field), but ANY NUMBER of secondary indexes.
Primary index¶
INDEX FILE (sparse: one entry per data block)
+----------+---------+ DATA FILE (sorted on Rollno)
| Rollno | pointer | +-------------------------+
+----------+---------+ | X2001 Ankit ... | block 1
| X2001 | ------------------> | X2002 Riya ... |
| X2011 | -------------. | X2003 Sana ... |
| X2021 | ---------. \ +-------------------------+
+----------+---------+ \ `--> | X2011 Arjun ... | block 2
3 entries for 3 blocks \ | X2012 Aditi ... |
\ | X2013 Rahul ... |
\ +-------------------------+
`--> | X2021 Neha ... | block 3
| X2022 Vikram ... |
+-------------------------+
The indexed value is the ANCHOR RECORD -- the first record of each block.
Search: binary-search the index for the largest anchor value ≤ the target, follow the pointer, then search within that one block.
Clustering index¶
The ordering field is not unique, so several records share a value.
INDEX (one entry per DISTINCT value) DATA FILE (sorted on Coursetype)
+------------+---------+ +-------------------------+
| Coursetype | pointer | | Fulltime CS01 ... | block 1
+------------+---------+ | Fulltime CH01 ... |
| Fulltime | ---------------> | Fulltime PH01 ... |
| Parttime | ------------. +-------------------------+
+------------+---------+ `----> | Parttime MA02 ... | block 2
| Parttime EN03 ... |
+-------------------------+
Points at the FIRST block containing that value; the rest follow.
Secondary index¶
The data file is not sorted on this field, so the index must be dense — every record needs its own entry, because nothing can be inferred about neighbours.
SECONDARY INDEX on Name (dense, sorted by Name)
+-----------------+---------+ DATA FILE (sorted on Rollno)
| Name | pointer | +-------------------------+
+-----------------+---------+ | X2001 Ankit ... |
| Aditi Rao | --------------. | X2002 Riya ... |
| Ankit Sharma | ---------. \ | X2003 Sana ... |
| Arjun Nair | ------. \ \ +-------------------------+
| Riya Verma | ---. \ \ `| X2011 Arjun ... |
| Sana Iqbal | -. \ \ `-----| X2012 Aditi ... |
+-----------------+---+ | \ | X2013 Rahul ... |
ONE ENTRY PER RECORD | `--------+-------------------------+
-- must be DENSE (order is unrelated to Name)
Why a secondary index must be dense
A sparse index works only because the data file is sorted on the indexed field: knowing where block k starts tells you that every value between anchor k and anchor k+1 is inside block k.
For a non-ordering field that inference is impossible — records with adjacent Name values may be in any blocks at all. So every record needs its own index entry.
Consequences: a secondary index is larger (one entry per record, not per block) and therefore costlier to search and maintain — but it provides an access path that would otherwise not exist at all.
Dense and sparse¶
Dense vs sparse
Dense index — an index entry for every record (or every distinct value) in the data file. Sparse (non-dense) index — an index entry for only some records, typically one per block.
| Dense | Sparse | |
|---|---|---|
| Entries | One per record | One per block |
| Size | Larger | Smaller |
| Search | Slightly faster | Slightly slower (must then scan within the block) |
| Requires the file to be sorted on the field? | No | Yes |
| Used by | Secondary indexes | Primary and clustering indexes |
| Can answer "does this value exist?" without touching the data file | Yes | No |
Comparison¶
| Primary | Clustering | Secondary | |
|---|---|---|---|
| Index field | Ordering key | Ordering non-key | Non-ordering |
| File sorted on it | Yes | Yes | No |
| Dense or sparse | Sparse | Sparse | Dense |
| Entries | One per block | One per distinct value | One per record |
| How many per file | At most one | At most one | Any number |
| Size | Smallest | Small | Largest |
25.3 Index Size and Search Cost¶
The calculation
Let r = records, R = record size, B = block size, V = index field size, P = pointer size.
Data file: bfr = floor(B/R), b = ceil(r/bfr).
Index: entry size Ri = V + P; index blocking factor bfri = floor(B/Ri).
Number of index entries ri = b for a primary index (one per block), or r for a dense secondary index.
Index blocks bi = ceil(ri / bfri).
Search cost = ceil(log₂ bi) + 1 — a binary search of the index, then one access to the data block.
Worked example¶
r = 30,000 records, R = 100 bytes, B = 1024 bytes, V = 9 bytes, P = 6 bytes.
Without an index (heap): bfr = 10, b = 3000 blocks. Linear search averages 1500 block accesses.
With a primary index (file sorted on the key):
- Entry size
Ri = 9 + 6 = 15bytes;bfri = floor(1024/15) = 68entries per block. - Entries
ri = b = 3000(one per data block);bi = ceil(3000/68) = **45** index blocks. - Search =
ceil(log₂ 45) + 1 = 6 + 1 = **7** block accesses.
Improvement: 1500 → 7, over 200-fold.
(For comparison, a binary search of the sorted data file alone would cost ceil(log₂ 3000) = 12. The index wins because it is 45 blocks rather than 3000.)
With a dense secondary index on a non-ordering field:
- Entries
ri = r = 30,000;bi = ceil(30000/68) = **442** index blocks. - Search =
ceil(log₂ 442) + 1 = 9 + 1 = **10** block accesses.
Still a 150-fold improvement on the linear scan, though costlier than the primary index because the index is ten times larger.
25.4 Multi-Level Indexes¶
The index is itself a sorted file, so it can be indexed in turn.
Multi-level index
Treat the index as a data file and build a primary index over it — the second level. Repeat until the top level fits in a single block.
Because each level is a sparse index over the level below, each level shrinks by a factor of fo, the fan-out (the index blocking factor bfri).
Number of levels t = ceil( log_fo (ri) ).
Search cost = t + 1 block accesses.
+-----------+
LEVEL 3 (top) | 1 block | <-- fits in one block: stop
+-----+-----+
+-----------+-----------+
| | |
LEVEL 2 +---+ +---+ +---+ 1 block (45/68 rounded up)
+-+-+ +-+-+ +-+-+
... ... ...
LEVEL 1 [45 blocks: the primary index]
... ... ...
DATA [3000 blocks, sorted]
Search: 1 (top) + 1 (level 2) + 1 (level 1) + 1 (data) = 4 accesses
compared with 7 for the single-level index and 1500 for a scan.
Worked example continued¶
The primary index had bi = 45 blocks with fan-out fo = 68.
- Level 1: 45 blocks (the index itself).
- Level 2:
ceil(45/68) = 1block — already a single block, so stop. - Levels
t= 2. Search cost =2 + 1 = **3** block accesses.
Summary of the whole progression:
| Method | Block accesses |
|---|---|
| Linear scan of a heap | 1500 |
| Binary search of the sorted file | 12 |
| Single-level primary index | 7 |
| Multi-level index | 3 |
Why the improvement is logarithmic in the fan-out
A binary search halves the search space each step: log₂ n.
A multi-level index divides it by the fan-out each step: log_fo n.
With fo = 68, each level does the work of log₂ 68 ≈ 6 binary-search steps. That is the entire advantage of tree-structured indexes, and it is why they are built with high fan-out — which in turn is why internal nodes are kept as small as possible.
25.5 B+-Trees¶
A static multi-level index suffers the same insertion problem as a sorted file: inserting a record may force the whole index to be reorganised. B-trees and B+-trees are dynamic multi-level indexes that keep themselves balanced.
B+-tree
A balanced tree in which:
- Internal nodes hold only search keys and tree pointers — no data pointers. They act purely as a directory.
- Leaf nodes hold all the search key values, each with its data pointer.
- Leaves are linked together in a chain, in key order.
- Every leaf is at the same depth — the tree is always balanced.
- Each node is kept at least half full, guaranteeing the depth bound.
+-------------+
INTERNAL (directory) | 30 | 60 | keys only, no data pointers
+--+---+---+--+
+------------+ | +------------+
| | |
+-----------+ +-------------+ +-----------+
| 10 | 20 | | 40 | 50 | | 70 | 80 |
+-+--+--+--+-+ +-+--+--+---+--+ +-+--+--+---+
| | | | | |
LEAVES (all data pointers live here, and leaves are CHAINED)
+--------+ +--------+ +--------+ +--------+ +--------+
|10,20->o|->|30,40->o |->|50,60->o |->|70,80->o |->|90,95->o |
+---+----+ +---+----+ +---+----+ +---+----+ +---+----+
| | | | |
v v v v v
D A T A R E C O R D S
The leaf chain makes a RANGE SCAN a simple sequential walk.
B-tree vs B+-tree¶
| B-tree | B+-tree | |
|---|---|---|
| Data pointers | In every node | Leaf nodes only |
| Key duplication | A key appears once | Keys may appear in internal nodes and leaves |
| Fan-out | Lower (nodes carry data pointers too) | Higher — so the tree is shallower |
| Leaves linked | No | Yes |
| Range queries | Awkward — requires tree traversal | Efficient — walk the leaf chain |
| Search cost | Varies; may end early at an internal node | Uniform — always reaches a leaf |
Why B+-trees won
-
Higher fan-out, shallower tree. Internal nodes carry only keys and tree pointers, not data pointers, so more entries fit in a block. With fan-out 100, three levels index a million records; four levels index a hundred million. Almost any lookup costs three or four block accesses.
-
Efficient range queries.
WHERE Rollno BETWEEN 'X2019' AND 'X2050'descends to the first matching leaf once, then follows the leaf chain sequentially. A B-tree would have to traverse up and down repeatedly. -
Uniform cost. Every search reaches a leaf, so performance is predictable — valuable for the query optimiser's cost estimates.
Consequence: the B+-tree is the default index structure in essentially every relational DBMS, and it is what CREATE INDEX builds unless you ask for something else.
Insertion, deletion and balance¶
Insertion. Find the correct leaf and insert in order. If the leaf overflows, split it into two, and promote the middle key to the parent. If the parent overflows, split it too — the split may propagate to the root, and splitting the root increases the tree's height by one. This is the only way a B+-tree grows, which is why every leaf stays at the same depth.
Deletion. Remove the entry. If the node falls below half full (underflow), borrow an entry from a sibling, or merge with a sibling and remove a key from the parent. Merging may propagate upward and can reduce the height.
The half-full guarantee is what bounds the height at log_(fo/2) n, so performance never degrades however the data arrives.
Practical consequences you can see in SQL
Composite index order matters. An index on (SID, Dateofadmission) is ordered by SID first. It therefore serves WHERE SID = ? and WHERE SID = ? AND Dateofadmission = ?, but not WHERE Dateofadmission = ? alone — a B+-tree searches by leading prefix.
A leading wildcard defeats the index. LIKE 'A%' can descend the tree; LIKE '%Sharma' cannot, because the tree is ordered by prefix.
Functions on the column defeat the index. WHERE YEAR(Dateofbirth) = 2001 must compute the function for every row. This is the sargability rule of Unit 4, Lesson 3, and the B+-tree is the reason for it.
Low-selectivity columns are poor candidates. An index on a two-valued Coursetype narrows the search to half the table; the optimiser will usually prefer a full scan, which reads blocks sequentially and so avoids the seek cost of many scattered index lookups.
CREATE INDEX idx_student_name ON STUDENT(Name);
CREATE INDEX idx_adm_sid_date ON ADMISSION(SID, Dateofadmission);
SHOW INDEX FROM STUDENT;
EXPLAIN SELECT * FROM STUDENT WHERE Name = 'Ankit Sharma'; -- was it used?
DROP INDEX idx_student_name ON STUDENT;
25.6 Solved Questions¶
Solved Question 1
Q. What is an index? Why is it needed, and what does it cost?
A. An index is an auxiliary access structure, stored separately from the data file, consisting of <field value, pointer> entries sorted on the field value. It speeds up retrieval of records satisfying a condition on the indexed field, without altering the data file.
Why needed. A file can be physically organised on only one field (Lesson 1). A STUDENT file sorted on Rollno gives no benefit whatever to WHERE Name = 'Ankit Sharma', which still costs a linear scan of b/2 blocks. An index provides an additional access path for any other field, and a file may have as many indexes as needed.
An index is fast because it is small: it stores one field and a pointer rather than whole records, so it occupies far fewer blocks and can be searched in far fewer accesses. For the example of Section 2.3, a search falls from 1500 block accesses to 7.
What it costs.
- Storage — sometimes a substantial fraction of the table's own size, especially for dense secondary indexes.
- Write penalty — every
INSERT,UPDATEandDELETEmust update every index on the table. A table with eight indexes performs writes many times more slowly than an unindexed one. - Maintenance — indexes fragment over time and need rebuilding.
So an index trades write speed and space for read speed. The rule is to index columns that appear in WHERE, join conditions and ORDER BY, and are reasonably selective — and to index nothing else.
Solved Question 2
Q. Distinguish primary, clustering and secondary indexes. Why must a secondary index be dense?
A. (Comparison table of Section 2.2.)
Primary index — on the ordering key field of a sorted file: the field is both the physical sort field and unique. Sparse, one entry per block, holding that block's anchor (first) record.
Clustering index — on the ordering field where values are not unique. Sparse, one entry per distinct value, pointing at the first block containing it.
Secondary index — on a non-ordering field. Dense, one entry per record.
A file can have at most one primary or clustering index, because it is physically sorted on only one field; it can have any number of secondary indexes.
Why a secondary index must be dense. A sparse index relies on an inference that only sorting makes valid: if anchor value v_k starts block k and v_{k+1} starts block k+1, then every record with a value between them lies in block k. One entry per block therefore suffices.
For a non-ordering field that inference collapses. Records with adjacent Name values may sit in completely unrelated blocks, since the file's physical order has nothing to do with Name. Knowing where "Ankit Sharma" is tells you nothing about where "Ankit Verma" is. Each record must therefore have its own index entry.
The consequence is that a secondary index has r entries rather than b — typically an order of magnitude more — so it occupies more blocks, costs more accesses to search, and is more expensive to maintain. It is nonetheless worth building, because the alternative is no access path at all.
Solved Question 3
Q. A file has 30,000 records of 100 bytes; block size 1024 bytes; index field 9 bytes; pointer 6 bytes. Compute the cost of a search with no index, with a single-level primary index, and with a multi-level index.
A.
The data file. bfr = floor(1024/100) = 10; b = ceil(30000/10) = 3000 blocks.
(a) No index — heap. Linear search averages b/2 = **1500** block accesses.
(b) Single-level primary index.
Entry size Ri = 9 + 6 = 15 bytes. Fan-out fo = bfri = floor(1024/15) = 68 entries per block.
A primary index is sparse, one entry per data block: ri = b = 3000 entries.
Index blocks bi = ceil(3000/68) = **45**.
Search = binary search of the index, then one data access:
ceil(log₂ 45) + 1 = 6 + 1 = **7** block accesses.
(c) Multi-level index.
- Level 1 = the 45-block index.
- Level 2 =
ceil(45/68) = 1block — a single block, so stop.t = 2levels. Search =t + 1 = **3** block accesses.
Comparison.
| Method | Accesses | Speed-up vs scan |
|---|---|---|
| Linear scan | 1500 | — |
| Binary search of the sorted data file | 12 | 125× |
| Single-level primary index | 7 | 214× |
| Multi-level index | 3 | 500× |
Comment. The multi-level index wins because each level divides the search space by the fan-out (68) rather than by 2. One level of a fan-out-68 index does the work of about six binary-search steps. At 10 ms per access, the search falls from 15 seconds to 30 milliseconds.
Solved Question 4
Q. Describe the structure of a B+-tree. How does it differ from a B-tree, and why is it preferred?
A. (Diagram: Section 2.5.) A B+-tree is a balanced multi-level index in which:
- Internal nodes hold only search keys and tree pointers — they are a pure directory with no data pointers.
- Leaf nodes hold every search key value together with its data pointer.
- Leaf nodes are linked in a chain in key order.
- All leaves are at the same depth, and every node is kept at least half full.
Differences from a B-tree. (Table of Section 2.5.) The essential one: a B-tree stores data pointers in every node, whereas a B+-tree stores them only in leaves.
Why B+-trees are preferred — three reasons.
-
Higher fan-out, hence a shallower tree. Internal nodes carry no data pointers, so more keys fit in a block. With a fan-out of 100, three levels address a million records and four address a hundred million — so essentially any lookup costs three or four block accesses, regardless of table size.
-
Efficient range queries.
WHERE Rollno BETWEEN 'X2019' AND 'X2050'descends the tree once to the first matching leaf, then follows the leaf chain sequentially. In a B-tree the same query requires repeated traversal up and down the tree, because successive keys are scattered across levels. Range andORDER BYqueries are extremely common, which makes this decisive. -
Uniform, predictable cost. Every search reaches a leaf, so every lookup costs the same number of accesses. A B-tree may terminate early at an internal node, making costs variable and harder for the query optimiser to estimate.
Consequently the B+-tree is the default index structure in essentially every relational DBMS.
Solved Question 5
Q. Explain insertion and deletion in a B+-tree, and how balance is maintained.
A.
Insertion.
- Descend from the root to the appropriate leaf and insert the key in sorted position.
- If the leaf still has room, stop.
- If it overflows, split it into two leaves, dividing the entries as evenly as possible, and promote a copy of the middle key to the parent as a separator. (A copy, because in a B+-tree every key must remain present in a leaf.) Relink the leaf chain.
- If the parent now overflows, split it too and promote its middle key — this time the key moves up rather than being copied, since internal nodes hold no data.
- Splits may propagate to the root. Splitting the root creates a new root and increases the height by one.
This is the only way a B+-tree grows — it grows at the root, not the leaves — which is precisely why every leaf remains at the same depth and the tree stays perfectly balanced without any explicit rebalancing operation.
Deletion. 1. Descend to the leaf and remove the entry. 2. If the node remains at least half full, stop. 3. If it underflows, first try to borrow (redistribute) an entry from an adjacent sibling that has more than the minimum, updating the separator key in the parent. 4. If no sibling can spare one, merge the node with a sibling and remove the now-redundant separator key from the parent. 5. A merge may cause the parent to underflow, propagating upward. If the root is left with a single child, the root is removed and the height decreases by one.
The balance guarantee. Because every node except the root is kept at least half full, a tree of height h with fan-out fo holds at least (fo/2)^h entries. Hence the height is bounded by log_(fo/2) n, and search, insertion and deletion are all O(log n) in the worst case, whatever order the data arrives in — including the sorted order that would degenerate an unbalanced tree into a linked list.
Solved Question 6
Q. Give four practical rules for deciding which columns to index, and explain each in terms of B+-tree structure.
A.
1. Index columns used in WHERE, join conditions and ORDER BY. These are the only places an index can be applied. A join in particular benefits enormously: without an index, each outer row triggers a full scan of the inner table.
2. Prefer highly selective columns. Selectivity is the fraction of rows a typical value matches. An index on Rollno (unique) narrows a search to one row; an index on a two-valued Coursetype narrows it only to half the table. In the latter case the optimiser will usually ignore the index and scan, because reading many scattered blocks via the index costs more seeks than reading the whole file sequentially (Lesson 1: seek time dominates). Indexing a low-selectivity column adds write cost for no read benefit.
3. Put the most selective — or most frequently filtered — column first in a composite index. A B+-tree is ordered by leading prefix. An index on (SID, Dateofadmission) serves WHERE SID = ? and WHERE SID = ? AND Dateofadmission = ?, but is useless for WHERE Dateofadmission = ? alone, since the tree's ordering says nothing about the second column independently of the first.
4. Keep the number of indexes small. Every INSERT, UPDATE and DELETE must update every index, and each update may cause node splits or merges that propagate up the tree. A table with eight indexes writes many times more slowly than an unindexed one.
Two corollaries that follow from the same structure:
- Do not wrap the indexed column in a function.
WHERE YEAR(Dateofbirth) = 2001cannot use the index, because the tree is ordered byDateofbirth, not byYEAR(Dateofbirth). Rewrite as a range — the sargability rule of Unit 4, Lesson 3. - Avoid a leading wildcard.
LIKE 'A%'descends the tree by prefix;LIKE '%Sharma'cannot, and forces a full scan.
Finally, primary keys and UNIQUE constraints are indexed automatically — never create a duplicate index on them.
25.7 Exercises¶
A. Short answer
- What is an index, and what does an index entry contain?
- Why can a file have at most one primary index but many secondary indexes?
- Distinguish dense from sparse indexes.
- Why must a secondary index be dense?
- What is the fan-out of an index, and why does it matter?
- Where are data pointers stored in a B+-tree?
- Give two reasons B+-trees are preferred to B-trees.
B. Computation
- A file has 100,000 records of 200 bytes; block size 4096 bytes; index field 12 bytes; pointer 8 bytes. Compute:
a.
bfrandbfor the data file. b. The fan-out of the index. c. The size and search cost of a single-level primary index. d. The size and search cost of a dense secondary index. e. The number of levels and search cost of a multi-level index. - Repeat question 8 for 1,000,000 records.
- An index has fan-out 100. How many levels are needed for 1000, 10⁶ and 10⁸ entries? What is the search cost in each case?
- Compare, in block accesses, a linear scan, a binary search of the sorted file, and a three-level index, for a file of 50,000 blocks.
C. Classification
- For each, state whether a primary, clustering or secondary index is appropriate, and whether it will be dense or sparse:
a.
STUDENTsorted onRollno, index onRollno. b. The same file, index onName. c.COURSEsorted onCoursetype, index onCoursetype. d.ADMISSIONas a heap, index onSID. e.EMPLOYEEsorted onDno, index onSsn.
D. Analysis
- For the college database, decide which indexes you would create, and justify each against the four rules of solved question 6. Which columns would you deliberately leave unindexed, and why?
- Explain why
WHERE Dateofadmission = '2019-07-15'cannot use an index on(SID, Dateofadmission). What index would serve it? - A developer adds an index to every column of a table and reports that inserts have become ten times slower. Explain, and give a method for deciding which indexes to drop.
- Explain why the optimiser may ignore an index on a low-selectivity column, referring to seek time.
- Show, step by step, the insertions of the keys 10, 20, 30, 40, 50 into an initially empty B+-tree of order 3 (at most 2 keys per node), drawing the tree after each split.
- Explain why a B+-tree grows at the root rather than at the leaves, and why this guarantees balance.
- A table is bulk-loaded with 10 million rows. Is it better to create the indexes before or after loading? Justify in terms of node splits.
E. Objective — True or False with reason
- An index changes the physical order of the data file.
- A primary index is dense.
- A file may have several clustering indexes.
- Internal nodes of a B+-tree contain data pointers.
- A B+-tree's leaves are linked.
- An index always speeds up a query.
- Creating an index changes the conceptual schema.
Answers to Section E
- False. An index is a separate structure; the data file is unchanged. (A clustered table in some systems does reorder data, but that is a different feature.)
- False. It is sparse — one entry per block, holding the block's anchor record.
- False. At most one, since the file is physically sorted on only one field.
- False. Internal nodes hold only keys and tree pointers; all data pointers are in the leaves. That is what gives the high fan-out.
- True. The leaf chain is what makes range scans and
ORDER BYefficient. - False. On a low-selectivity column the optimiser may correctly prefer a sequential scan; and the index always slows down writes.
- False. It is an internal-level change — physical data independence (Unit 1, Lesson 3).
Lesson Summary
- An index is a separate
<value, pointer>structure giving an extra access path; it trades write speed and space for read speed. - Primary (ordering key, sparse, one per block), clustering (ordering non-key, sparse, one per value), secondary (non-ordering, must be dense, one per record). At most one primary or clustering index; any number of secondary.
- Multi-level indexes divide the search space by the fan-out at each level, giving
log_fo nrather thanlog₂ n. - B+-trees keep data pointers only in leaves (high fan-out, shallow tree) and chain the leaves (efficient range scans); they stay balanced by splitting at the root.
- Index selective columns used in
WHERE, joins andORDER BY; respect the leading-prefix rule for composite indexes; keep the column bare in the predicate.