Reducing the Memory Overhead of Search Indexes

26 concepts25 papers1 proposal

To search a massive dataset efficiently, we rarely scan the raw data sequentially. Instead, we build indexes—like B+ trees, tries, or inverted files—that allow us to locate specific records in logarithmic or constant time. However, as datasets scale to billions of items, a critical bottleneck emerges: the index itself can become so massive that it fails to fit within the system's random-access memory (RAM).

When an index exceeds available RAM, the system is forced to rely on secondary disk storage. Because disk I/O introduces orders of magnitude more latency than memory lookups, keeping the index compact enough to reside entirely in memory is paramount for high-performance retrieval. Research in memory-constrained indexing focuses on understanding why traditional indexes bloat and designing mechanisms to eliminate this structural waste.

The Hidden Cost of Pointers and Structure

The primary culprit behind index bloat is not the data being indexed, but the structural metadata required to navigate it. In traditional hierarchical structures like tries or suffix trees, every node contains explicit pointers to its children. On modern 64-bit architectures, each pointer consumes 8 bytes. If a node only represents a single character or a small integer, the memory spent on pointers can completely dwarf the actual payload.

To combat this "pointer tax," researchers have turned to succinct data structures and structural compression. The core intuition is to replace explicit pointers with implicit mathematical relationships. For example, in A Succinct N-gram Language Model, Taro Watanabe et al. utilize a Level-Order Unary Degree Sequence (LOUDS) to represent tree topologies as compact bit vectors. Instead of traversing a pointer, the system performs fast bit-count operations to calculate child positions on the fly, drastically lowering the memory footprint of large language models.

Other approaches target the keys themselves or the relationship between the index and the source text. Huanchen Zhang et al. introduced an order-preserving key compression framework in Order-Preserving Key Compression for In-Memory Search Trees that shrinks string keys dynamically while maintaining their alphabetical sorting, accelerating lookups while saving up to 30% of RAM. In string matching, traditional compressed indices often store pointers back to the original source text to resolve edge labels. To break this memory-heavy dependency, Diptarama Hendrian et al. designed online algorithms in Online Algorithms for Constructing Linear-size Suffix Trie to build linear-size suffix structures that operate independently of the source text layout.

When the underlying data is highly repetitive or hierarchical, such as XML documents, the structure can be optimized by transforming trees into Directed Acyclic Graphs (DAGs). As demonstrated in Path Queries on Compressed XML, sharing identical subtrees allows million-node documents to be queried entirely within main memory by eliminating redundant structural branches.

The Multi-Index Explosion

The memory challenge compounds when a system must support complex queries, such as multi-attribute filtering, range constraints, or high-dimensional vector searches. To serve these queries quickly, databases frequently construct multiple independent or multi-level indexes over the same underlying dataset.

This architectural choice creates a massive redundancy multiplier. As Andreas Kipf et al. observe in LSI: A Learned Secondary Index Structure, conventional secondary indexes that store sorted key-pointer pairs often consume more memory than the actual data they point to. Similarly, when handling range-constrained approximate nearest neighbor searches (e.g., "find similar items created within a specific time window"), multi-level indexing can inflate the storage footprint by 3x to 14x compared to a standard single-index setup, as detailed by Joshua Engels et al. in Approximate Nearest Neighbor Search with Window Filters.

To break this compounding overhead, researchers look for ways to trade query-time computation for space savings, or replace explicit tables with functional approximations:

  • Algorithmic Probing: Instead of building multiple redundant hash tables to ensure high accuracy in high-dimensional spaces, Rina Panigrahy demonstrates in Entropy based Nearest Neighbor Search in High Dimensions that a system can hash multiple randomly generated points in the neighborhood of a query. This shifts the burden from memory capacity to CPU cycles.
  • Learned Approximations: Rather than storing explicit pointers for every sorted key, learned indexes use compact mathematical models (like splines or linear regressions) to predict the position of a key within an array, achieving massive space reductions without sacrificing lookup speeds.

Intelligent Tiering and Hybrid Layouts

When a dataset is so vast that its index absolutely cannot fit entirely within RAM, the goal shifts to minimizing the impact of disk latency through intelligent tiering. Instead of treating the index as a monolithic structure that is either completely in memory or completely on disk, hybrid architectures split the index based on access patterns or structural depth.

In GHOST: Fine Granularity Buffering of Indexes, Beng Chin Ooi et al. propose a dual-buffering strategy that bypasses traditional top-down tree traversals. Instead of caching intermediate directory pages of a tree in memory, the system caches direct pointers to "hot" leaf pages in a compact Splay-tree. This allows the system to jump straight to the data records, keeping the memory footprint minimal while avoiding the I/O penalty of navigating a disk-bound hierarchy.

Traditional Traversal:
[Root (RAM)] -> [Internal Node (Disk I/O)] -> [Leaf Node (Disk I/O)]

GHOST Traversal:
[Hot Leaf Cache (RAM)] ----------------------> [Leaf Node (Disk I/O)]

A similar philosophy applies to large-scale language processing. Chun-Liang Chen et al. designed the CPAT tree in CPAT-Tree-Based Language Models with an Application for Text Verification in Chinese by splitting a suffix-based tree into a small, highly active in-memory component and a larger, sequential on-disk component. By isolating the structural metadata needed for initial routing from the bulkier tail of the index, these hybrid approaches ensure that memory-constrained hardware can still process complex, large-scale queries efficiently.

Key Foundational Work

CPAT-Tree-Based Language Models with an Application for Text Verification in Chinese (1998) — contributed 1 concept elements to this direction.
Stratified Case-Based Reasoning: Reusing Hierarchical Problem Solving Episodes (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_memory_constrained_indexing_a65a4e2e,
  title = {memory-constrained indexing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-indexing/rdr_a65a4e2e120b44369ca9cf5c549f080b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_memory_constrained_indexing_a65a4e2e_v1,
  title = {memory-constrained indexing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-indexing/rdr_a65a4e2e120b44369ca9cf5c549f080b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake