Indexing is an essential data structure technique designed to speed up search operations by reducing the number of physical disk block accesses required to retrieve rows.
Indexing Classifications
| Index Type | Key Order Alignment | Index density | Description |
|---|---|---|---|
| Primary Index | Ordered key matches table structure. | Usually Sparse | Defined on the primary key of an ordered data file. Only one primary index can exist. |
| Clustering Index | Non-key field ordered matches table. | Sparse | Defined on a non-key ordered field (e.g., grouping employees by Department ID). |
| Secondary Index | Table physical order is independent of index key. | Dense | Defined on unordered fields (e.g., creating an index on email field). Multiple secondary indexes are allowed. |
Index Dense vs Sparse
B-Tree vs B+ Tree Node Layout
Database engines use B+ Trees for relational indexes due to their physical layout advantages:
| Feature | B-Tree | B+ Tree |
|---|---|---|
| Data pointers | Stored in both leaf and non-leaf nodes. | Stored only in leaf nodes. Non-leaf nodes only store search key values to route queries. |
| Leaf linking | Leaf nodes are not linked together. | Leaf nodes are connected sequentially in a doubly linked list. |
| Range Queries | Slow. Requires executing in-order traversal (up and down the tree). | Fast. Locate the starting key in a leaf, then traverse the linked list. |
| Internal Node capacity | Low, because data pointers occupy space in internal nodes. | High. Can store many child pointers, leading to a much wider fan-out and shorter tree. |