How ScyllaDB’s Trie-Based Index Delivers Up to 3X More Throughput

By transitioning from separate summary and index files to a prefix tree, we optimized cache efficiency, reduced disk I/O, and reduced memory overhead

Trie-based SSTable index format was added in ScyllaDB 2025.4. Since then, it has evolved and matured to become the default index format in ScyllaDB 2026.2.

In this post, we deep dive into the format change, present its pros and cons, and show our latest benchmark results of the legacy vs. Trie index formats.

For benchmarking, we chose four different read workloads that would benefit from the Trie index format in different degrees. For all four, Trie indexes demonstrated better performance. They achieved 20% to 230% higher throughput and 31% to 63% lower latency compared to legacy indexes. The impact of Trie index on the write path is negligible.

Note that for use cases with either very low cache usage or 100% row-cache hit rate, the performance gain is expected to be lower. However, these use cases are unlikely in production.

Trie Index Usage in ScyllaDB

Before explaining the new format, we will cover the legacy index format and its challenges.

Legacy Three-Layer Lookup (me/md format)

Until ScyllaDB 2026.2 the default storage format was the SSTable version md and me.

Every SSTable lookup in the me/md format traverses three or four structures:

• Summary.db (entirely in RAM)
• Binary search in Index.db
• Sequential read in Data.db

Both the partition index and the clustering-row index are stored in Index.db. The partition index is partially represented in memory by the sampled Summary.db, while the clustering-row index exists as a promoted index for large partitions.

┌──────── MEMORY ──────────────────────────────┐
│                                              │
│  Summary.db  (entirely in RAM)               │
│  ─────────────────────────────               │
│  Sampled at ~1 byte per ~2000 bytes of       │
│  Data.db                                     │
│                                              │
│  "aardvark" → Index.db byte        0         │
│  "kangaroo" → Index.db byte  1,048,576       │
│  "platypus" → Index.db byte  2,097,152       │
│  "zebra"    → Index.db byte  3,145,728       │
│                                              │
└──────────────────┬───────────────────────────┘
                   │
       binary search → window in Index.db
                   │
                   ▼
┌──────── DISK ────────────────────────────────┐
│                                              │
│  Index.db                                    │
│  ─────────                                   │
│  "kangaroo"   → Data.db: 4,096,000           │
│  "koala"      → Data.db: 4,097,280           │
│  "kookaburra" → Data.db: 4,098,560           │
│  "lemur"      → Data.db: 4,099,840  ← found  │
│  ... (up to ~800 entries per 1 MB scan)      │
│                                              │
└──────────────────┬───────────────────────────┘
                   │
       1 seek + sequential read
                   │
                   ▼
┌──────── DISK ────────────────────────────────┐
│  Data.db                                     │
│  <partition data>                            │
└──────────────────────────────────────────────┘

For partitions containing enough clustering rows, a fourth structure is involved:

Index.db entry for a large partition
┌──────────────────────────────────────────┐
│  partition key  → Data.db offset         │
│  promoted_index (flat list of CK blocks) │
│    block 0: ck_start="aaa", ck_end="azz" │
│    block 1: ck_start="baa", ck_end="bzz" │
│    ...                                   │
│    block N: ck_start=...,  ck_end=...    │
│    offsets[0..N]  ← binary search here   │
└──────────────────────────────────────────┘

The New Trie Index Format

The Trie index replaces Summary.db + Index.db with a single on-disk prefix tree. The storage format is compatible with Apache Cassandra’s BTI (Big Trie Index) format, implemented using ScyllaDB’s Seastar architecture.

Trie indexes are used for both partition indexes and clustering key indexes.

What Is a Trie?

A trie (prefix tree) stores keys character-by-character. Shared prefixes occupy a single path, eliminating redundancy:

Keys: "kangaroo", "koala", "kookaburra", "lemur", "lion"

            [root]
            /    \
          'k'    'l'
           |      |
          [k]    [l]
          / \    / \
        'a' 'o''e' 'i'
         |   |  |   |
        'n' [o]'m' 'i'
         |  / \ |   |
        'g''a' 'o''u' 'o'
         |  |  |  |   |
        'a''l' 'k''r' 'n'
         |  |  |  *
        'r''a' 'a'    * = leaf node
         |  *  |       (payload: Data.db offset)
        'o'   'b'
         |     |
        'o'   'u'
         *     |
              'r'
               |
              'r'
               |
              'a'
               *

"k", "ko", "koo" — shared prefixes stored ONCE

New SSTable Files

The ms/mt format replaces Summary.db and Index.db with two purpose-built files:

SSTable (ms format)
├── Data.db
│     unchanged — partition and row data,
│     same binary layout as me/md
│
├── Partitions.db                     ← NEW
│     Trie index:
│       partition key → Data.db offset
│         (small partitions)
│       partition key → Rows.db offset
│         (large partitions)
│
│     ┌── Page 0 (4,096 bytes) ───────┐
│     │  trie root node [1]           │
│     │  + children (fan-out ≤ 256)   │
│     │  + their children (packed)    │
│     └───────────────────────────────┘
│     ┌── Page 1 (4,096 bytes) ───────┐
│     │  subtree for keys 'a'–'g'     │
│     └───────────────────────────────┘
│     ...
│     ┌── Footer ─────────────────────┐
│     │  first_key      (raw bytes)   │
│     │  last_key       (raw bytes)   │
│     │  partition_count (uint64)     │
│     │  trie_root_pos  (uint64)      │
│     └───────────────────────────────┘
│
├── Rows.db                            ← NEW
│     Per-partition clustering-key
│     tries, concatenated.
│     Each sub-trie:
│       clustering key → byte-offset
│         within partition
│     (replaces flat "promoted index"
│      in Index.db)
│
├── Filter.db     bloom filter — unchanged
├── Statistics.db statistics  — unchanged
└── Scylla.db     ScyllaDB metadata — unchanged

[1] Parent nodes are always written after their child nodes. Parents point to children, so child positions must be known before parents are written.

How a Partition Lookup Works

Query: SELECT * FROM orders
       WHERE order_id = 'ORD-20240611-98765'

┌─────────────────────────────────────────┐
│  Step 1 — Key Translation               │
│                                         │
│  'ORD-20240611-98765'                   │
│         ↓  bti_key_translation.cc       │
│  comparable byte sequence               │
│  (lexicographic order matches           │
│   CQL semantic order)                   │
└──────────────────┬──────────────────────┘
                   │
┌──────────────────▼──────────────────────┐
│  Step 2 — Trie Traversal                │
│           in Partitions.db              │
│                                         │
│  Read root page (4 KB)                  │
│    ← usually in OS page cache           │
│                                         │
│  [root] ──'O'──> [node]  (page 0)       │
│  [node] ──'R'──> [node]  (page 0)       │
│  [node] ──'D'──> [node]  (fetch page 1) │
│  [node] ──'-'──> [node]  (page 1)       │
│  ...                                    │
│  [leaf] payload = Data.db or            │
│                   Rows.db pos 2,097,152 │
│                                         │
│  Typical: 2–6 page fetches.             │
│  Top pages cached → often 0–1 disk I/Os │
└──────────────────┬──────────────────────┘
                   │
┌──────────────────▼──────────────────────┐
│  Step 3 — Read Data.db                  │
│  Seek to offset 2,097,152               │
│  → read partition header                │
│  For large partitions: read Rows.db     │
└──────────────────┬──────────────────────┘
                   │  (range/clustering queries only)
┌──────────────────▼──────────────────────┐
│  Step 4 — Read Data.db at position      │
│           returned from index           │
└─────────────────────────────────────────┘

Page Layout: Packing Parent and Children Together

The most critical write-time optimization is ensuring that a node and its children land on the same 4 KB page. This means an entire trie neighborhood is readable in a single I/O, even on the first (cold) access.

┌──────── 4,096-byte page ────────────────┐
│                                         │
│  [A] ──'p'──> [B] ──'p'──> [C]         │
│         │                │              │
│         └──'r'──> [D]    ├──'l'──>[E]* │
│                          │              │
│                          └──'y'──>[F]* │
│                                         │
│  (* = leaf node with payload)           │
│  (padding bytes to align next subtree         │
│   to page boundary)                     │
└─────────────────────────────────────────┘

trie_writer algorithm (trie_writer.hh):

  1. Maintain rightmost path root → current
     node (_stack)
  2. On each new key: branch off rightmost
     path, add new nodes
  3. Accumulate nodes until a finished
     subtree exceeds a page
  4. Flush child subtrees with padding so
     each subtree fits within one page

ScyllaDB vs. Cassandra reference impl:

  Cassandra: one character per node
  ScyllaDB:  characters grouped into
             "chains" (up to 300 bytes)
  → dramatically faster writes for long
    keys, same read-side page structure

Old vs. New: Side-by-Side Summary

Benchmark Results

The following table shows the key results, measured at client-side P99 ≤ 10 ms on a 3-node AWS production-class cluster. All tests were run on 3 × i8g.2xlarge instances, each on a different zone, with Replication Factor (RF) of 3.

Discussion: Why Trie Indexes Improve Performance, and When to Use Them

ScyllaDB CTO Avi Kivity has mentioned three reasons why Trie indexes improve performance:

• Improved cacheability: the index is denser, so it is more likely to fit in cache, requiring no I/O for the index itself.
• Fewer I/O operations after cache miss: if the index is not in cache, fewer I/O operations are required to fetch it since the index is more compact and shallower. This is especially true for large partitions, often seen in materialized view workloads.
• CPU efficiency: less CPU is needed to process the index during reads.

A possible downside is that more CPU is needed to create the index during memtable flush and compaction. However, this is more than offset by the read-side advantages.

Summary

ScyllaDB 2026.2 has adopted a Trie-based index format as its new default, replacing the legacy index structure to significantly enhance read path performance. By transitioning from separate summary and index files to a prefix tree, this design optimizes cache efficiency, reduces disk I/O, and reduces memory overhead. Benchmarks indicate that this architectural change delivers throughput improvements ranging up to 3x across various workloads, offering a more scalable and efficient solution than the legacy index format.

As always, actual results depend on your workload. To evaluate the gain of Trie index, we highly recommend testing it yourself with the latest ScyllaDB releases.