Index Entry

An index, regardless of its type or implementation, is ultimately a collection of index entries. Each entry is the atomic unit of information that the index stores and organizes. Understanding index entries is understanding indexes at the most fundamental level.

An index entry answers a simple question: "Given this search key value, where can I find the corresponding data?" But the way this question is answered—what information is included, how it is formatted, how duplicates are handled—varies significantly across database systems and index configurations. These variations have profound implications for space efficiency, lookup performance, update cost, and concurrency behavior.

At its core, an index entry consists of two fundamental components:

Index Entry = Search Key Value + Data Reference

Search Key Value:

This is the value (or combination of values for composite keys) extracted from the indexed column(s). The key value is what makes the entry findable—index traversal algorithms compare the search predicate against key values to locate matching entries.

• For an index on employee_id: The key might be 10042
• For an index on last_name: The key might be 'Smith'
• For a composite index on (department, hire_date): The key might be ('Engineering', '2023-01-15')

Data Reference:

This component tells us where to find the actual data record. The nature of this reference varies dramatically across index designs and determines much of the index's behavior. The three main alternatives are explored in detail in subsequent sections.

Additional Entry Components:

Beyond the basic key-reference pair, index entries often include:

1. Entry Length Field: For variable-length entries, indicates total entry size
2. Key Length Field: For variable-length keys, indicates key size
3. Null Indicator: Bitmap or flag indicating which key components are null
4. Timestamp/Version: In MVCC systems, indicates entry visibility
5. Delete Marker: Indicates logically deleted entries awaiting garbage collection
6. Compression Metadata: For prefix-compressed entries, reconstruction information

The physical format of an entry is carefully designed to minimize space while enabling efficient byte-level operations. Real-world entries are packed structures with no wasted bytes.

In this design, the index entry is the data record itself. The data is stored directly within the index structure, organized by the search key. There is no separate data file; the index contains all the data.

Conceptual Structure:

┌─────────────────────────────────────────────────────────┐
│ Index Entry = (Search Key Value, Full Data Record)      │
│                                                         │
│ Example:                                                │
│ (10042, {emp_id:10042, name:'Smith', dept:'Eng', ...}) │
└─────────────────────────────────────────────────────────┘

This is the design used by clustered indexes (also called primary indexes in some contexts). The data is physically arranged in the order of the index key.

When to Use This Design:

• When there is a natural ordering key that dominates query patterns
• When range queries on that key are common and performance-critical
• When the table is predominantly read-heavy after initial load
• When the key values rarely change (to avoid costly record movement)

This is the default table organization in systems like InnoDB, where every table has a clustered index on its primary key (or a hidden row ID if no primary key is defined).

In this design, the index entry contains the search key value and a record identifier (RID) pointing to the data record's location. The data resides in a separate heap file or clustered index.

Conceptual Structure:

┌────────────────────────────────────────────────────────┐
│ Index Entry = (Search Key Value, RID)                  │
│                                                        │
│ RID typically = (Page Number, Slot Number)             │
│                                                        │
│ Example:                                               │
│ ('Smith', Page:1042, Slot:7)                           │
└────────────────────────────────────────────────────────┘

This is the design used by secondary indexes (non-clustered indexes) in most database systems. Each entry is a compact pointer to a data record.

Handling Duplicate Keys:

When multiple records share the same key value, there are two sub-approaches:

2a. One entry per record (duplicate entries):

('Smith', Page:1042, Slot:7)
('Smith', Page:1089, Slot:3)
('Smith', Page:2001, Slot:15)

• Simple structure; each entry is self-contained
• Key value repeated, consuming more space
• Direct point lookup to each record

2b. One entry per unique key (list of RIDs):

('Smith', [RID:1042.7, RID:1089.3, RID:2001.15])

• Key value stored once; space-efficient for high-duplicate keys
• Variable-length entries complicate storage management
• Must manage RID list growth and overflow

Most systems use 2a (one entry per record) for simplicity, accepting the space overhead in exchange for uniform entry sizes and simpler concurrency control.

This variation consolidates all RIDs for a given key value into a single index entry. Instead of repeating the key for each matching record, the key appears once with an associated list of record pointers.

Conceptual Structure:

┌───────────────────────────────────────────────────────────────┐
│ Index Entry = (Search Key Value, RID List)                    │
│                                                               │
│ Example:                                                      │
│ ('Engineering', [RID:101.3, RID:104.7, RID:107.2, RID:203.1])│
└───────────────────────────────────────────────────────────────┘

This design is particularly interesting for columns with many duplicates—such as department names, status codes, or category identifiers.

Implementation Challenges:

1. Variable-length entries: RID list length varies by key. Some keys may have millions of RIDs, others may have one.

2. Entry growth: When a new record with an existing key is inserted, the entry must grow. This may require:

   • In-place expansion (if page has space)
   • Entry relocation to a different page
   • Overflow pages for very long lists

3. Concurrency complexity: Updating an entry that may be read-locked by other transactions requires careful protocol design.

4. Deletion challenges: Removing one RID from a list requires locating it within potentially millions of entries.

Typical Implementation: Overflow Pages

For keys with very many duplicates, most implementations use overflow pages:

• The index entry stores the key and a pointer to a chain of overflow pages
• Overflow pages contain RID lists and pointers to subsequent overflow pages
• Acts like a linked list of RID blocks

Index entries must be stored on disk pages, and their physical layout significantly affects performance. Understanding entry storage helps explain why certain operations are fast or slow.

Page Layout for Index Entries:

A typical B+-tree leaf page contains:

┌──────────────────────────────────────────────────────┐
│ Page Header (LSN, flags, pointers)        ~20 bytes │
├──────────────────────────────────────────────────────┤
│ Entry 1: (key₁, RID₁)                               │
│ Entry 2: (key₂, RID₂)                               │
│ Entry 3: (key₃, RID₃)                               │
│ ...                                                  │
│ Entry N: (keyₙ, RIDₙ)                               │
├──────────────────────────────────────────────────────┤
│ Free Space                                           │
├──────────────────────────────────────────────────────┤
│ Slot Directory (offsets to entries)      ~2N bytes  │
│ Page Trailer                              ~8 bytes  │
└──────────────────────────────────────────────────────┘

Entries are typically stored in key order, with a slot directory at the page bottom pointing to each entry. This allows binary search within the page.

Fixed-Length vs. Variable-Length Entries:

Fixed-Length Entries:

• All entries occupy the same space (max key size + RID size)
• Simple to manage: entry N is at offset N × entry_size
• Wastes space when actual keys are shorter than maximum
• Common for integer keys or short fixed-length strings

Variable-Length Entries:

• Each entry occupies only the space needed
• Requires slot directory or length prefixes to locate entries
• More complex insertion/deletion (may require compaction)
• Essential for VARCHAR keys or composite keys with variable components

Key Compression Techniques:

To improve fanout (entries per page), databases employ compression:

1. Prefix Compression: For sequential keys, store only the differing suffix

   • Keys: 'application', 'apply', 'appointment'
   • Stored: 'application', '+ly' (diff from prev), '+ointment'

2. Suffix Truncation: In internal nodes, store only enough of the key to distinguish children

   • Full key: 'Bartholomew'
   • Truncated separator: 'Bar' (if sufficient to route)

While we've focused on B+-tree entries, different index types have different entry structures optimized for their use cases.

B+-Tree Leaf Entries:

• Contain (key, RID) or (key, data)
• Sorted by key within the page
• Linked to sibling leaves for range scans
• Support: equality, range, prefix matching, ordering

B+-Tree Internal Entries:

• Contain (key, child_page_pointer)
• Keys serve as separators (routing guides)
• No RIDs or data—purely navigational
• Often use suffix truncation for space efficiency

Hash Index Entries:

• Contain (key, RID) within hash buckets
• No ordering within buckets
• Bucket determined by hash(key) mod bucket_count
• Support: equality only (no range queries)

Bitmap Index Entries:

• Fundamentally different structure
• Entry per distinct key value: (key, bit_vector)
• Bit vector has one bit per row in the table
• Bit is 1 if that row has this key value, 0 otherwise
• Supports: equality, AND/OR operations efficiently

Full-Text Index Entries (Inverted Index):

• Entry per distinct term: (term, posting_list)
• Posting list: list of (document_id, position, frequency) tuples
• Optimized for text search, not exact equality
• Supports: keyword search, phrase matching, relevance ranking

Spatial Index Entries (R-tree):

• Entry per spatial object: (bounding_box, RID)
• Objects grouped by spatial proximity
• Bounding boxes may overlap (unlike B+-trees)
• Supports: contains, intersects, nearest-neighbor queries

Every aspect of index entry design involves trade-offs. Understanding these trade-offs enables you to reason about why databases make the choices they do and how to configure indexes for specific workloads.

Trade-off 1: Entry Size vs. Feature Set

Covering indexes (including extra columns for index-only scans) exemplify this trade-off: larger entries eliminate table lookups but increase index size and write costs.

Trade-off 2: Pointer Format

InnoDB chose primary key as pointer; PostgreSQL uses RID (ctid). Each has valid rationale.

Trade-off 3: Duplicate Handling