Indexing Strategies

How your database conquest going on, we have learned how data is stored pages in different layouts (row and column oriented) and how database uses buffering to reduce the latency even further!

However, as our dataset grows, even reading from the buffer pool isn’t always fast enough, especially when we need to search for a specific value or range within a massive table. That’s where indexing strategies enter the scene, acting like a smart, optimised roadmap to our data.

The indexing strategy directly impacts how data is physically stored on disk. And there are different types of indexing strategy (different ways of storing data) optimised for different workloads.

Alright! before we move on to all these different type of indexing strategies, we will see nemesis of large databases, which is fragmentation.

Fragmentation is what happens when data pages and files on disk get scattered, leaving gaps and empty spaces over time. As records are inserted, updated, and deleted, the once neatly organised pages start breaking apart, leading to inefficient storage and slower queries.

Imagine trying to read a book where the pages are randomly spread out across different shelves, we’d waste time jumping around just to read a single chapter.

In databases, this means more disk seeks, poor cache utilisation, and degraded performance.

While fragmentation will eventually build up (no matter what) as data is inserted, updated, and deleted, indexing strategies can help control and mitigate it by enforcing order and enabling periodic reorganisation. For example, B+ Trees maintain a sorted structure, so inserts and deletes trigger internal balancing (splits and merges) that reduce scattered storage. On the other hand, LSM Trees delay fragmentation by first writing sequentially to memory and disk, and then compacting and merging files in the background, actively cleaning up fragmented data. This way, the index structure not only speeds up lookups but also plays a role in keeping data organised and reclaiming fragmented space over time.

Heap Storage

This strategy is actually not a strategy, and just unordered pages.

The database engine simply looks for any available free space in existing pages using the free space map (FSM). If no page has enough space, a new page is allocated. A new record can go into any page with space. Over time, this leads to fragmentation, where related rows are scattered across different pages, for example, sequentially inserted rows might end up on completely different memory locations. Which means they are definitely not good for range queries, as most of the times, a full scan is needed to locate specific rows (though, non-clustered indexes can help searches by pointing to these random pages).

Clustered Index Storage (ordered and B+ Tree structure)

In this strategy, pages are organised (physically in the disk) based on the primary key (also called as, clustered index). Each page corresponds to a node in a B+ Tree, and data is inserted such that the sorted order of B+ Tree is maintained.

For example, when inserting a new row of data, the B+ Tree is traversed to locate the correct page for insertion. If the target page is full, a page split occurs, where the existing data is split between the old page and a new page and parent nodes in the B+ Tree are updated to maintain the property. This leads to page balancing to maintain efficient search paths.

This makes it efficient for range queries because data is stored contiguously, also, its fast for lookups (if using the indexed key), as the B+ Tree guides the search.

Append-Only Storage (log-structured using LSM Trees)

Data is always written sequentially in pages to a log (or Memtable in memory), and when this Memtable becomes full, it is flushed to disk as a sorted immutable file (SSTable) and each flush creates a new immutable SSTable, which means over time, many small SSTables can accumulate, so for that a compaction process (expensive background process) merges smaller SSTables into larger, more efficient ones, reducing redundancy, and reducing fragmentation.

LSM Trees are optimised for write-heavy workloads (for example, logs, time-series data). And they have slower reads because multiple SSTables might need to be scanned. Old pages remain untouched (immutability), leading to simpler writes but costly reads if compaction is delayed. It is used in Cassandra, RocksDB, LevelDB, Bigtable.

Hash Index Storage

Each data insertion is hashed to get a key pointing to a set of pages (called as bucket). This provides constant-time lookup O(1) for exact queries (WHERE id = 123), but not suitable for range queries since hashes don’t preserve order, for example, some data might be in one bucket and some data might be in other bucket (based on the calculated hash).

When a page is full, an overflow page is created to store additional rows. However, if inconsistent hashing is used, over time, multiple overflow pages can be chained, leading to potential read inefficiencies.

Hash Index Storage is used in Redis, Memcached, PostgreSQL Hash Indexes.

Conclusion

To conclude, these strategies significantly speed up read operations but can also introduce additional I/O overhead during writes.