Sparse index: entry per granule

11 / 34Machine translation

← →

1 · INTERNALS · INDEX

-- индекс части 202609_1_9_1
SELECT mark_number, event_type,
       `toDate(ts)`, player_id
FROM mergeTreeIndex('lesson04', 'events');
--   0  damage    2026-09-01      1
--   1  damage    2026-09-01  16580
-- 180  damage    2026-09-30  98874
-- 181  kill      2026-09-01  37335
-- …    301 гранула, ≈2 КиБ в памяти

One entry per granule, not per line. A granule consists of up to 8,192 consecutive lines. The index entry is the key of the first line in the granule. Query: index → desired granules → marks → read only those.

GRANULE

marks

Reading Unit

marks file

The order of the key is important

The entire data block is read just for a single row—up to 8,192 rows of the relevant columns.

event_type.cmrk2: For each granule—the offset in the compressed event_type.bin file.

The first column represents binary search. The third column represents brute-force search with exclusion, which is less efficient.

A B-tree would store 2.46 million records—one per row. A sparse index finds a range of granules rather than a row: it is small and does not check for uniqueness.