Single-Level Indexing

A single-level index is a flat index file where each index entry contains a search key value and a pointer to the corresponding data records. The index file itself is sor

What is Single-Level Indexing?

A single-level index is a flat index file where each index entry contains a search key value and a pointer to the corresponding data record(s). The index file itself is sorted by the search key, allowing binary search.

Index File (sorted by key)	Data File:
│ Key │ Pointer │ │ Block 1	[R1][R2] │
├──────────┼──────────┤ ┌──────►│ Block 2	[R3][R4] │
│ K1 │	Block1 │─────┘ │ Block 3: [R5][R6] │
│ K2 │	Block2 │─────────────► Block 4: [R7][R8] │
│ K3 │	Block3 │ └─────────────────────┘
│ K4 │	Block4 │

Types of Single-Level Indexes

1. Primary Index

Built on the ordering key field of a physically ordered (sequential) file.

One index entry per data block (not per record)
Index entry contains: (first key value in block, pointer to block)
Always a sparse index
The data file must be ordered on the same key

E101	→ Block1
E104	→ Block2
E107	→ Block3

Properties:

Number of index entries = Number of data blocks
Smaller index file → faster binary search
Data file must be physically ordered on the key

2. Clustering Index (Cluster Index)

Built on a non-key ordering attribute — the data file is ordered on this attribute, but it is not the primary key (so multiple records can have the same value).

One index entry per distinct value of the clustering field
Pointer points to the first block containing that value

D1	→ Block1
D2	→ Block2
D3	→ Block3

3. Secondary Index

Built on a non-ordering field — the data file is NOT physically ordered on this attribute.

Can be dense (one entry per record) or use bucket pointers
Often uses an extra level of indirection (bucket of pointers)
Multiple secondary indexes allowed per table

55000	→ {Block2, Slot1}
62000	→ {Block1, Slot2}
71000	→ {Block2, Slot2}
75000	→ {Block1, Slot1}
88000	→ {Block1, Slot3}
90000	→ {Block2, Slot3}

Dense vs. Sparse Index

Dense Index

One index entry for every record in the data file
Can find any record directly from the index

E101	→Blk1,S1	────►	Block 1: [E101]
E102	→Blk1,S2	────►	[E102]
E103	→Blk1,S3	────►	[E103]
E104	→Blk2,S1	►	Block 2: [E104]

Sparse Index

One index entry for every data block (not every record)
Smaller index file, but requires sequential scan within a block after locating the block

E101	→Block1	────►	Block 1: [E101][E102]
E104	→Block2	────►	Block 2: [E104][E105]

Comparison Table

Index Type	Data File Order	# Entries	Key Type	Dense?
Primary	Ordered on key	One per block	Unique key	Sparse
Clustering	Ordered on non-key	One per distinct value	Non-unique	Sparse
Secondary	Any order	One per record	Any attribute	Dense

Index Search Cost

Binary search on index	⌈log₂(b_i)⌉ block accesses
Then	1 block access to retrieve the data record.
Table: 1,000,000 records, 10 records/block	100,000 data blocks
Primary index: 100,000 entries, 100 entries/block	1,000 index blocks
Binary search	log₂(1000) ≈ 10 block reads + 1 data block = 11 total
vs. full table scan	100,000 block reads!

What is Single-Level Indexing?

Index File (sorted by key)	Data File:
│ Key │ Pointer │ │ Block 1	[R1][R2] │
├──────────┼──────────┤ ┌──────►│ Block 2	[R3][R4] │
│ K1 │	Block1 │─────┘ │ Block 3: [R5][R6] │
│ K2 │	Block2 │─────────────► Block 4: [R7][R8] │
│ K3 │	Block3 │ └─────────────────────┘
│ K4 │	Block4 │

Types of Single-Level Indexes

1. Primary Index

Built on the ordering key field of a physically ordered (sequential) file.

One index entry per data block (not per record)
Index entry contains: (first key value in block, pointer to block)
Always a sparse index
The data file must be ordered on the same key

E101	→ Block1
E104	→ Block2
E107	→ Block3

Properties:

Number of index entries = Number of data blocks
Smaller index file → faster binary search
Data file must be physically ordered on the key

2. Clustering Index (Cluster Index)

Built on a non-key ordering attribute — the data file is ordered on this attribute, but it is not the primary key (so multiple records can have the same value).

One index entry per distinct value of the clustering field
Pointer points to the first block containing that value

D1	→ Block1
D2	→ Block2
D3	→ Block3

3. Secondary Index

Built on a non-ordering field — the data file is NOT physically ordered on this attribute.

Can be dense (one entry per record) or use bucket pointers
Often uses an extra level of indirection (bucket of pointers)
Multiple secondary indexes allowed per table

55000	→ {Block2, Slot1}
62000	→ {Block1, Slot2}
71000	→ {Block2, Slot2}
75000	→ {Block1, Slot1}
88000	→ {Block1, Slot3}
90000	→ {Block2, Slot3}

Dense vs. Sparse Index

Dense Index

One index entry for every record in the data file
Can find any record directly from the index

E101	→Blk1,S1	────►	Block 1: [E101]
E102	→Blk1,S2	────►	[E102]
E103	→Blk1,S3	────►	[E103]
E104	→Blk2,S1	►	Block 2: [E104]

Sparse Index

One index entry for every data block (not every record)
Smaller index file, but requires sequential scan within a block after locating the block

E101	→Block1	────►	Block 1: [E101][E102]
E104	→Block2	────►	Block 2: [E104][E105]

Comparison Table

Index Type	Data File Order	# Entries	Key Type	Dense?
Primary	Ordered on key	One per block	Unique key	Sparse
Clustering	Ordered on non-key	One per distinct value	Non-unique	Sparse
Secondary	Any order	One per record	Any attribute	Dense

Index Search Cost

Binary search on index	⌈log₂(b_i)⌉ block accesses
Then	1 block access to retrieve the data record.
Table: 1,000,000 records, 10 records/block	100,000 data blocks
Primary index: 100,000 entries, 100 entries/block	1,000 index blocks
Binary search	log₂(1000) ≈ 10 block reads + 1 data block = 11 total
vs. full table scan	100,000 block reads!

Single-Level Indexing

What is Single-Level Indexing?

Types of Single-Level Indexes

1. Primary Index

2. Clustering Index (Cluster Index)

3. Secondary Index

Dense vs. Sparse Index

Dense Index

Sparse Index

Comparison Table

Index Search Cost

Continue learning this concept

Single-Level Indexing

What is Single-Level Indexing?

Types of Single-Level Indexes

1. Primary Index

2. Clustering Index (Cluster Index)

3. Secondary Index

Dense vs. Sparse Index

Dense Index

Sparse Index

Comparison Table

Index Search Cost

Continue learning this concept