Skip to content

Internals

Key index

Fast node lookups by key

Every node in KiteDB can have a string key. The key index maps keys to node IDs with O(1) average-case lookups.

The problem

Applications usually find nodes by an identifier they already have, such as a username or an external ID. Without an index, that lookup is a scan.

Without an index

Find the node with key user:alice

Scan every node and compare its key.

O(n)grows with the number of nodes
With the hash index

Find the node with key user:alice

Hash the key and read one bucket.

O(1)average case

Measured p50: 42 ns

The measured figure is the p50 for random existing keys on the Rust core, 10k nodes, 50k edges, read from the snapshot index after a checkpoint (October 3, 2026, Apple M5 Pro, MVCC on). See the benchmarks for the full results.

Index structure

The snapshot stores the key index as two arrays: a bucket array of offsets and an entry array sorted by bucket. Each bucket is a contiguous run of entries, so there is no probing.

Snapshot key index
Bucket arrayKeyBuckets · u32 × (num_buckets + 1)
0
0
1
1
2
1
3
3
4
4
 
…

Bucket b owns entries key_buckets[b] up to key_buckets[b + 1]. Here bucket 2 holds entries 1 and 2; bucket 1 is empty.

Entry arrayKeyEntries · 24 B each, sorted by bucket, then hash
8 B4 B4 B8 B
0
hash64string_idreservednode_id
bucket 0
1
hash64string_idreservednode_id
bucket 2
2
hash64string_idreservednode_id
bucket 2
3
hash64string_idreservednode_id
bucket 3
hash64
xxHash64 of the key string
string_id
Index of the key in the snapshot string table, used to confirm a match
reserved
4 bytes, written as zero
node_id
The node this key maps to

Lookup process

1

Check the delta

If the key is in delta.key_index_deleted, return null.
If the key is in delta.key_index, return its node ID.
2

Find the bucket in the snapshot

hash = xxhash64(key)
bucket = hash % num_buckets
start = key_buckets[bucket]
end = key_buckets[bucket + 1]
3

Scan the bucket

Skip entries where entry.hash64 != hash.
On a hash match, compare string_table[entry.string_id] with the key.
If the strings are equal, return entry.node_id. If no entry matches, return null.

Two-level lookup

The key index is split between the delta in memory and the snapshot on disk:

Two-level lookup
Deltain memory
key_index
HashMap<String, NodeId>
key_index_deleted
HashSet<String>
Snapshotmemory-mapped file
KeyBuckets
u32[]
KeyEntries
{hash64, string_id, node_id}[]

Lookup order

  1. 1delta.key_index_deletedfound: return null
  2. 2delta.key_indexfound: return the node ID
  3. 3snapshot indexhash, then scan one bucket

Deletions are checked first, so a key deleted since the last checkpoint is not found in the snapshot. Inside a transaction, its own uncommitted key changes are checked before the delta.

Why xxHash64

What the index needs from a hash
Fast
Computed once per lookup, and once per key when a checkpoint builds the index.
Even distribution
Spreads keys across buckets so most buckets hold zero or one entry.
Deterministic
Hashes are stored in the snapshot, so a key must hash to the same value in every process. KiteDB uses seed 0.

xxHash64

Non-cryptographic, 64-bit output, designed for throughput.

SHA-256

Cryptographic. The extra work per byte buys resistance to deliberate collisions, which a local key index does not need.

Handling collisions

When two keys share a hash

Two keys with the same 64-bit hash (illustrative values)

"user:alice"hash0x1234…
"user:alfred"hash0x1234…same hash
  1. 1Both entries sit in the same bucket.
  2. 2The lookup hash matches both entries.
  3. 3For each match, the stored key is read from the string table through string_id.
  4. 4The entry whose stored key equals the lookup key is returned.

Keys that only share a bucket are cheaper: the hash64 comparison skips them without reading a string. String comparisons happen once per entry with the same 64-bit hash, so the cost is O(k) for k such entries, and k is almost always 1.

Load factor

Load factor

load factor = entries / buckets

A checkpoint sizes the bucket array at max(16, 2 × entries), so the load factor is at most 50%.

1002101001020000

8 keys in 16 buckets: most buckets hold zero or one entry, which keeps collisions rare and bucket scans short.

Index size for 1M keys

Bucket array2M × 4 B8 MB
Entry array1M × 24 B24 MB
Total~32 MB

The key strings themselves live in the snapshot string table. A hit reads two adjacent bucket offsets, one or two entries, and one string.

Next steps