Ordered, primary, clustering and secondary indexes

Why it exists

Even a sorted file needs a dozen block reads to find one record, and only for its sort field. An index is a small separate file of (key, pointer) entries, like the index of a book: it finds the block of a record with a few reads. This page covers the classical ordered indexes; trees that stay balanced under insertions follow (B trees, B+ trees).

Prerequisites

You need blocks, the blocking factor and the cost of searching a file (file organisation).

Precise definitions

An index on a field (the indexing field) of a file is a file of entries $\langle \text{value}, \text{pointer} \rangle$ ordered by the value. Terminology differs between books; the definitions below follow the textbook of Elmasri and Navathe, which GATE questions follow:

A dense index has an entry for every search-key value (every record); a sparse index has entries for only some values, so a search finds the entry with the largest value $\le$ the key and then reads that block.

Because the data file can be ordered by only one field, a file has at most one primary or clustering index (one of them), but any number of secondary indexes.

Notation: $B$ block size, $V$ size of the indexing field, $P$ size of a block pointer; an index entry occupies $V + P$ bytes. The index blocking factor is $bfi = \lfloor B / (V + P) \rfloor$.

How it works

Sizes and the cost of a search

Take $B = 1024$, record size $R = 100$, $r = 30\,000$ records, $V = 9$, $P = 6$. Then $bf = 10$, $b = 3000$ data blocks and $bfi = \lfloor 1024/15 \rfloor = 68$.

• Primary index (sparse, one entry per data block): $3000$ entries, $\lceil 3000/68 \rceil = 45$ index blocks. A binary search of the index takes $\lceil \log_2 45 \rceil = 6$ accesses, plus $1$ for the data block: $7$ accesses, instead of $\lceil \log_2 3000 \rceil = 12$ without an index.
• Secondary index on a key field (dense, one entry per record): $30\,000$ entries, $\lceil 30\,000/68 \rceil = 442$ blocks. Binary search $\lceil \log_2 442 \rceil = 9$, plus $1$: $10$ accesses, instead of $1500$ on average for a linear scan of the unordered file.
• Clustering index: one entry per distinct value of the clustering field.

The search of the primary index was run on a generated file with real index blocks: at most $7$ block reads for the keys tried, the formula's value.

Multilevel indexes

If the index itself is large, make an index on the index: the first-level index is a sorted file, so a second-level index with one entry per first-level block can be built, and so on until the top level fits in one block. A search reads one block per level and then the data block.

• Primary index: levels of $45$ and $1$ blocks ($\lceil 45/68 \rceil = 1$): two levels, so a search reads $2 + 1 = 3$ blocks (measured: exactly $3$ for every key tried).
• Secondary index: levels of $442$, $7$ and $1$ blocks: three levels, so $3 + 1 = 4$ blocks.

The number of levels is the smallest $t$ with $bfi^{\,t} \ge$ (number of first-level entries), i.e. $t = \lceil \log_{bfi} (\text{first-level entries}) \rceil$ (verified on 2000 random cases). A multilevel index is a static tree: it is correct for a file that does not change; with insertions it needs overflow blocks and reorganisation. The balanced dynamic version is the B+ tree.

Maintenance and trade-offs

• Every insertion or deletion in the data file must also update every index; a dense index needs an entry per record. A file with many secondary indexes has slower updates.
• A primary index entry points to the first record of a block; inserting into a sorted file may shift records and change anchor values, so ordered files are costly to keep ordered (overflow blocks, deferred reorganisation).
• Indexes speed up equality and range searches on the indexed field; a search on a non-indexed field still scans the file.
• A secondary index on a non-key field has either one entry per record (many entries with the same value) or one entry per distinct value pointing to a block of record pointers (an extra level of indirection).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The cost model comes from file organisation; the dynamic, balanced version of a multilevel index is the B+ tree (B+ trees), and the B tree stores records pointers in all nodes (B trees).

PYQs

Consider a relational table r with sufficient number of
records, having attributes A1, A2,..., An and let 1 <= p
<= n. Two queries Q1 and Q2 are given below.

Q1:
 π A1, A2, ..., Ap ( σ Ap = c ( r ) ) where c is a constant.

Q2:
 π A1, A2, ..., Ap ( σ c1 ≤ Ap ≤ c2 ( r ) ) where c1 and c2 are
constants.

The database can be configured to do ordered indexing
on Ap or hashing on Ap. Which of the following
statements is TRUE?

An index in a DBMS is said to be dense if an index entry
appears for every search-key value in the indexed file.
Otherwise it is called a sparse index. Consider the
following two statements:

S1: A hash index must be a dense index
S2: A B+ tree index can be a sparse index

Which one of the following options is correct?

Consider a database of fixed-length records, stored as an
ordered file. The database has 25,000 records, with each
record being 100 bytes, of which the primary key
occupies 15 bytes. The data file is block-aligned in that
each data record is fully contained within a block. The
database is indexed by a primary index file, which is also
stored as a block-aligned ordered file. The figure below
depicts this indexing scheme.

Suppose the block size of the file system is 1024 bytes,
and a pointer to a block occupies 5 bytes. The system
uses binary search on the index file to search for a
record with a given key. You may assume that a binary
search on an index file of b blocks takes ⌈log2b⌉ block
accesses in the worst case.
Given a key, the number of block accesses required to
identify the block in the data file that may contain a
record with the key, in the worst case, is _____

A data file consisting of 1,50,000 student-records is stored
on a hard disk with block size of 4096 bytes. The data file
is sorted on the primary key RollNo. The size of a record
pointer for this disk is 7 bytes. Each student-record has a
candidate key attribute called ANum of size 12 bytes.
Suppose an index file with records consisting of two fields,
ANum value and the record pointer to the corresponding
student record, is built and stored on the same disk. Assume
that the records of data file and index file are not split
across disk blocks. The number of blocks in the index file
is____.?

A file is  organized so that the ordering of   data records
is the same as or close to the ordering of data  entries in
some index. Then that index  is called

An index is clustered, if

A clustering index is defined on the fields which are of
type

Consider a file of 16384 records. Each record is 32
bytes long and its key field is of size 6 bytes. The file is
ordered on a non-key field, and the file organization is
unspanned. The file is stored in a file system with block
size 1024 bytes, and the size of a block pointer is 10
bytes. If the secondary index is built on the key field of
the file, and a multilevel index scheme is used to store
the secondary index, then the number of first-level and
second-level blocks in the multilevel index are
respectively:

Self-check

Revision card

References