Data Structures in LevelDB — Go & Python

The insert path in one picture
1. Internal Key
2. Skip List
3. MemTable
4. Write-Ahead Log (WAL)
5. SSTable (Sorted String Table)
6. Min-Heap (K-way Merge)
7. Red-Black Tree
8. B-Tree
9. B+ Tree
Summary: all data structures compared
Summary: data structures touched by db.Put("name","Alice")

This guide maps every data structure used across labs 01–08 to the exact Go source in this repo, then shows a Python equivalent you can run in a REPL. Every example is anchored to the same scenario: inserting the three key-value pairs ("age","25"), ("city","London"), and ("name","Alice") — the same data used in the lab demos.

The insert path in one picture

db.Put("name","Alice")
        │
        ├─► 1. Encode Internal Key  ────────────────────────────────────────────────┐
        │       "name" || uint64(seqNum<<8 | TypeValue) — 8 extra bytes             │
        │                                                                            │
        ├─► 2. WAL.Append(record)   ──────► disk: [4B len][4B crc][payload]          │
        │       fdatasync guarantees durability before anything in-memory changes    │
        │                                                                            │
        ├─► 3. SkipList.Put(internalKey, value)  ◄───────────────────────────────────┘
        │       probabilistic sorted linked list; O(log n) insert
        │
        │   (when MemTable ≥ 4 MiB) ─────────────────────────────────────────────────
        ├─► 4. SSTable Builder.Add(internalKey, value)  ← iterator over SkipList
        │       varint-encoded records + in-memory index; fdatasync on Finish
        │
        │   (when L0 ≥ 4 files) ──────────────────────────────────────────────────────
        └─► 5. Min-Heap merge (K-way merge)
                priority queue over all L0+L1 iterators; dedup by MVCC seqNum

1. Internal Key

Concept

Every key stored in the MemTable and in SSTables is an internal key:

internal key = userKey  ||  tag (8 bytes, little-endian)

where tag = (seqNum << 8) | keyType
      seqNum: monotonically increasing write counter (uint64)
      keyType: 0 = deletion tombstone, 1 = value

Sort order: user key ascending, then sequence number descending. This means ("name", seqNum=5) sorts before ("name", seqNum=3), so a forward scan always encounters the most recent version first.

Go implementation (`lab02/key.go`)

// KeyType distinguishes a value record from a deletion marker.
type KeyType uint8

const (
    TypeDelete KeyType = 0
    TypeValue  KeyType = 1
)

// EncodeInternalKey builds:  userKey || uint64(seqNum<<8 | kt)  little-endian.
func EncodeInternalKey(userKey []byte, seqNum uint64, kt KeyType) []byte {
    buf := make([]byte, len(userKey)+8)
    copy(buf, userKey)
    tag := (seqNum << 8) | uint64(kt)
    binary.LittleEndian.PutUint64(buf[len(userKey):], tag)
    return buf
}

// DecodeInternalKey splits back into components.
func DecodeInternalKey(b []byte) (userKey []byte, seqNum uint64, kt KeyType) {
    tag := binary.LittleEndian.Uint64(b[len(b)-8:])
    return b[:len(b)-8], tag >> 8, KeyType(tag & 0xff)
}

// CompareInternal: userKey ASC, seqNum DESC.
func CompareInternal(a, b []byte) int {
    ukA, seqA, _ := DecodeInternalKey(a)
    ukB, seqB, _ := DecodeInternalKey(b)
    if c := bytes.Compare(ukA, ukB); c != 0 {
        return c
    }
    if seqA > seqB { return -1 }
    if seqA < seqB { return  1 }
    return 0
}

Python implementation

import struct

TYPE_DELETE = 0
TYPE_VALUE  = 1

def encode_internal_key(user_key: bytes, seq_num: int, key_type: int) -> bytes:
    """
    Encodes user_key + (seq_num << 8 | key_type) as 8 bytes little-endian.

    >>> k = encode_internal_key(b"name", 3, TYPE_VALUE)
    >>> k[:4]
    b'name'
    >>> int.from_bytes(k[4:], 'little') == (3 << 8 | TYPE_VALUE)
    True
    """
    tag = (seq_num << 8) | key_type
    return user_key + struct.pack('<Q', tag)   # '<Q' = little-endian uint64

def decode_internal_key(b: bytes) -> tuple[bytes, int, int]:
    """Returns (user_key, seq_num, key_type)."""
    tag = struct.unpack('<Q', b[-8:])[0]
    return b[:-8], tag >> 8, tag & 0xFF

def compare_internal(a: bytes, b: bytes) -> int:
    """Returns -1, 0, or 1.  user_key ASC, seq_num DESC."""
    uk_a, seq_a, _ = decode_internal_key(a)
    uk_b, seq_b, _ = decode_internal_key(b)
    if uk_a < uk_b: return -1
    if uk_a > uk_b: return  1
    # same user key — higher seqNum sorts first (descending)
    if seq_a > seq_b: return -1
    if seq_a < seq_b: return  1
    return 0

Example: `Put("name","Alice")` at seqNum=3

key = encode_internal_key(b"name", 3, TYPE_VALUE)
print(key.hex())
# 6e616d65 01 03 00 00 00 00 00 00
#  "name"  ↑   ↑── seqNum=3 stored in tag (little-endian)
#         type=1

user_key, seq, kt = decode_internal_key(key)
print(user_key, seq, kt)   # b'name' 3 1

The full 12-byte internal key in hex:

6e 61 6d 65  01 03 00 00 00 00 00 00
 n  a  m  e  └────── tag LE: (3<<8|1) = 0x0301 ──────┘

In real database engines

LevelDB (db/dbformat.h, db/dbformat.cc) The exact same layout: user_key + PackSequenceAndType(seq, type) where PackSequenceAndType = (seq << 8) | type. The comparator InternalKeyComparator::Compare mirrors CompareInternal above. Every MemTable entry, every SSTable record, and every iterator key is an internal key — the user never sees the 8-byte suffix.

RocksDB (include/rocksdb/types.h, db/dbformat.h) Identical tag layout. RocksDB adds two extra key types:

kTypeMerge = 2 — merge operator result (partial updates, e.g. increment a counter without read-modify-write)
kTypeBlobIndex = 18 — key whose value lives in a separate blob file (BlobDB)

The sequence number is 56 bits (not 64) — the top 8 bits encode the type, giving room for type codes up to 255 while keeping the tag in one uint64.

Pebble (CockroachDB’s storage engine, internal/base/internal_key.go) Same 8-byte tag, same comparator direction. Pebble adds InternalKeyKindRangeDelete and InternalKeyKindRangeKeySet for efficient range tombstones — instead of one tombstone per key, a single record covers [start, end) and is encoded as a special boundary key in SSTable metadata blocks.

Badger (value.go) Badger separates large values into a value log (vlog) file — the MemTable stores (internalKey → valuePointer{fileID, offset, len}) instead of the value directly, keeping the skip list compact. The tag byte is extended to distinguish BitValuePointer from inline values.

Key design lesson: the 8-byte tag appended to every key is the minimal representation of a logical clock. Any storage engine that needs MVCC, snapshot reads, or crash-safe deletes without in-place updates will arrive at the same or an equivalent design.

2. Skip List

Concept

A skip list is a layered singly-linked list. Level 0 contains all nodes in sorted order. Each higher level is a probabilistic 25%-sampled subset of the level below. A search starts at the highest level and drops down, giving O(log n) expected time for both lookups and inserts — the same as a balanced BST — but without any rebalancing.

Level 3:  head ──────────────────────────── "name,5" ─────── nil
Level 2:  head ──────── "city,7" ─────────── "name,5" ─────── nil
Level 1:  head ─ "age,2" ─ "city,7" ──────── "name,5" ─────── nil
Level 0:  head ─ "age,2" ─ "city,7" ─ "city,6" ─ "name,5" ── nil
                                         ↑ older version of "city"

Go implementation (`lab02/skiplist.go`)

const (
    maxLevel = 12    // max tower height
    prob     = 0.25  // 25% chance to promote to next level
)

type node struct {
    key   []byte
    value []byte
    next  [maxLevel]*node
}

type SkipList struct {
    head   *node
    length int
    level  int
}

func randomLevel() int {
    lvl := 1
    for lvl < maxLevel && rand.Float64() < prob {
        lvl++
    }
    return lvl
}

func (sl *SkipList) Put(key, value []byte) {
    // update[i] = rightmost node at level i that is < key
    var update [maxLevel]*node
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.next[i] != nil && CompareInternal(cur.next[i].key, key) < 0 {
            cur = cur.next[i]
        }
        update[i] = cur
    }

    // Exact match? Update in-place.
    if n := update[0].next[0]; n != nil && CompareInternal(n.key, key) == 0 {
        n.value = value
        return
    }

    lvl := randomLevel()
    if lvl > sl.level {
        for i := sl.level; i < lvl; i++ { update[i] = sl.head }
        sl.level = lvl
    }
    n := &node{key: key, value: value}
    for i := 0; i < lvl; i++ {
        n.next[i] = update[i].next[i]
        update[i].next[i] = n
    }
    sl.length++
}

Python implementation

import random
from typing import Optional

MAX_LEVEL = 12
PROB      = 0.25

class _Node:
    __slots__ = ('key', 'value', 'next')
    def __init__(self, key: bytes, value: bytes, level: int):
        self.key   = key
        self.value = value
        self.next: list[Optional['_Node']] = [None] * level

def _random_level() -> int:
    lvl = 1
    while lvl < MAX_LEVEL and random.random() < PROB:
        lvl += 1
    return lvl

class SkipList:
    """Probabilistic sorted map keyed by internal keys."""
    def __init__(self):
        self._head  = _Node(b'', b'', MAX_LEVEL)
        self._level = 1
        self._len   = 0

    def put(self, key: bytes, value: bytes):
        update = [None] * MAX_LEVEL
        cur = self._head
        for i in range(self._level - 1, -1, -1):
            while (cur.next[i] is not None and
                   compare_internal(cur.next[i].key, key) < 0):
                cur = cur.next[i]
            update[i] = cur

        nxt = update[0].next[0]
        if nxt is not None and compare_internal(nxt.key, key) == 0:
            nxt.value = value   # exact match: update in-place
            return

        lvl = _random_level()
        if lvl > self._level:
            for i in range(self._level, lvl):
                update[i] = self._head
            self._level = lvl

        n = _Node(key, value, lvl)
        for i in range(lvl):
            n.next[i] = update[i].next[i]
            update[i].next[i] = n
        self._len += 1

    def get(self, key: bytes) -> Optional[bytes]:
        cur = self._head
        for i in range(self._level - 1, -1, -1):
            while (cur.next[i] is not None and
                   compare_internal(cur.next[i].key, key) < 0):
                cur = cur.next[i]
        nxt = cur.next[0]
        if nxt is not None and compare_internal(nxt.key, key) == 0:
            return nxt.value
        return None

    def __iter__(self):
        """Yields (key, value) in CompareInternal order."""
        cur = self._head.next[0]
        while cur is not None:
            yield cur.key, cur.value
            cur = cur.next[0]

Example: insert out-of-order, read back sorted

sl = SkipList()
sl.put(encode_internal_key(b"name",  3, TYPE_VALUE), b"Alice")
sl.put(encode_internal_key(b"age",   1, TYPE_VALUE), b"25")
sl.put(encode_internal_key(b"city",  2, TYPE_VALUE), b"London")

for ik, val in sl:
    uk, seq, kt = decode_internal_key(ik)
    print(f"  {uk.decode():8s} seq={seq}  ->  {val.decode()}")

Output — always sorted regardless of insert order:

  age      seq=1  ->  25
  city     seq=2  ->  London
  name     seq=3  ->  Alice

MVCC: overwrite “city” at a higher seqNum

sl.put(encode_internal_key(b"city", 7, TYPE_VALUE), b"Paris")

for ik, val in sl:
    uk, seq, kt = decode_internal_key(ik)
    print(f"  {uk.decode():8s} seq={seq}  ->  {val.decode()}")

Output — both versions exist; newer (seq=7) sorts first:

  age      seq=1  ->  25
  city     seq=7  ->  Paris    <- newer version first (seqNum DESC)
  city     seq=2  ->  London   <- older version second
  name     seq=3  ->  Alice

A read at readSeq=5 sees “London”; a read at readSeq=8 sees “Paris”.

In real database engines

LevelDB (db/skiplist.h) The skip list is a single-threaded writer, multi-threaded reader design. Inserts are protected by a mutex in DBImpl; readers traverse without any locks because nodes are only ever added (never deleted from) the list, and pointer writes are sequentially consistent. The maximum level is 12; promotion probability is 1/4, giving ~4.3 nodes on average per key.

RocksDB (memtable/skiplist.h, memtable/inlineskiplist.h) RocksDB provides three MemTable implementations configurable at runtime:

SkipList — same design as LevelDB
InlineSkipList — key stored inline in the node (no extra heap allocation), CAS-based concurrent inserts without a global write lock
HashSkipList — hash table of per-bucket skip lists; O(1) point lookup, O(n) full scan
HashLinkedList — hash table of sorted singly-linked lists; lower memory than skip lists for small buckets

The concurrent InlineSkipList uses a std::atomic<Node*> for each next pointer and compare_exchange_weak to splice a new node in — this is the lock-free insert you cannot easily do with a red-black tree.

Apache Cassandra (org.apache.cassandra.db.Memtable) Cassandra’s MemTable is a ConcurrentSkipListMap<DecoratedKey, ColumnFamily> (Java stdlib). Flush is triggered by heap pressure (JVM GC), not just byte count. Multiple MemTables may be flushing concurrently while a fresh one accepts new writes — the same immutable MemTable pattern as LevelDB.

Redis sorted sets (t_zset.c) Redis uses a skip list with 32 levels (not 12) and promotion probability 1/4. The skip list is paired with a hash table in the zset struct:

typedef struct zset {
    dict     *dict;   // hash: member → score  (O(1) lookup)
    zskiplist *zsl;   // skip list sorted by score (O(log n) rank/range)
} zset;

ZRANGEBYSCORE, ZRANK, and ZRANGE all use the skip list. ZSCORE uses the hash table. This dual-index design is only viable because both structures are in-memory — on-disk you would use a B+ tree for both.

3. MemTable

Concept

MemTable wraps the skip list and manages the MVCC sequence number. It is the in-memory write buffer: every db.Put and db.Delete lands here first. When its size exceeds flushThreshold (4 MiB), it is frozen as immutable and flushed to an SSTable file on disk.

Go implementation (`lab02/memtable.go`)

type MemTable struct {
    sl   *SkipList
    size int  // approximate bytes
}

// Add inserts one mutation — encodes the internal key then delegates.
func (m *MemTable) Add(seqNum uint64, kt KeyType, key, value []byte) {
    ikey := EncodeInternalKey(key, seqNum, kt)
    m.sl.Put(ikey, value)
    m.size += len(ikey) + len(value)
}

// Get returns the latest version of key visible at readSeq.
func (m *MemTable) Get(key []byte, readSeq uint64) ([]byte, bool) {
    seekKey := EncodeInternalKey(key, readSeq, TypeValue)
    it := m.sl.NewIter()
    it.Seek(seekKey)
    if !it.Valid() { return nil, false }
    uk, seq, kt := DecodeInternalKey(it.Key())
    if !bytes.Equal(uk, key) || seq > readSeq { return nil, false }
    if kt == TypeDelete { return nil, false }
    return it.Value(), true
}

Python implementation

class MemTable:
    def __init__(self):
        self._sl   = SkipList()
        self._size = 0

    def add(self, seq_num: int, key_type: int, key: bytes, value: bytes):
        ikey = encode_internal_key(key, seq_num, key_type)
        self._sl.put(ikey, value)
        self._size += len(ikey) + len(value)

    @property
    def approximate_size(self) -> int:
        return self._size

    def get(self, key: bytes, read_seq: int) -> Optional[bytes]:
        seek_key = encode_internal_key(key, read_seq, TYPE_VALUE)
        for ik, val in self._sl:
            if compare_internal(ik, seek_key) < 0:
                continue
            uk, seq, kt = decode_internal_key(ik)
            if uk != key:
                return None
            if seq > read_seq:
                continue
            if kt == TYPE_DELETE:
                return None
            return val
        return None

Example: full Put → Get trace, overwrite, delete

mem = MemTable()
mem.add(1, TYPE_VALUE,  b"age",  b"25")
mem.add(2, TYPE_VALUE,  b"city", b"London")
mem.add(3, TYPE_VALUE,  b"name", b"Alice")

print(mem.get(b"name", 3))    # b'Alice'
print(mem.get(b"city", 3))    # b'London'

# Overwrite "city" at seqNum=7
mem.add(7, TYPE_VALUE, b"city", b"Paris")
print(mem.get(b"city", 7))    # b'Paris'  <- new version
print(mem.get(b"city", 2))    # b'London' <- old snapshot still sees London

# Delete "age" at seqNum=10
mem.add(10, TYPE_DELETE, b"age", b"")
print(mem.get(b"age", 10))    # None   <- tombstone hides the key
print(mem.get(b"age",  1))    # b'25'  <- seqNum=1 predates the delete

In real database engines

LevelDB (db/memtable.h, db/memtable.cc) One active MemTable + at most one immutable MemTable being flushed. The flush pipeline:

DBImpl::MakeRoomForWrite() — if active MemTable ≥ write_buffer_size (4 MiB default), rotate it to immutable and open a fresh one.
Background thread calls CompactMemTable() → WriteLevel0Table() → BuildTable() → TableBuilder::Finish().
Once the SSTable is fsync’d, the WAL segment covering those writes is deleted.

The MemTable holds a reference count; the WAL deletion is safe only when the reference drops to zero (no active iterator over the immutable table).

RocksDB (db/memtable.h, memtable/) RocksDB allows multiple concurrent active MemTables (max_write_buffer_number). This hides flush latency: while one MemTable is being flushed (potentially taking hundreds of milliseconds on a slow disk), the next MemTable absorbs new writes. Atomic flush mode can flush all column families’ MemTables atomically to avoid cross-CF consistency issues.

Apache HBase (HStore, MemStore) HBase is built on HDFS; every flush creates a new StoreFile (HFile, an SSTable variant). HBase supports two MemStore implementations:

DefaultMemStore — ConcurrentSkipListMap (like Cassandra)
CompactingMemStore — in-memory compaction before flush, reducing the number of SSTables on L0

ScyllaDB (C++ reimplementation of Cassandra) ScyllaDB uses a per-CPU shard model: each shard owns its own MemTable and never shares memory with other shards (no lock contention). Flush is triggered by a configurable dirty memory fraction of the shard’s memory pool, not a global byte threshold.

Key design lesson: the MemTable is the only mutable component in an LSM tree. Every design decision in LevelDB — the WAL (durability), the immutable MemTable (zero-copy flush), the sequence number (snapshot reads) — exists to let this small, fast in-memory structure absorb writes safely.

4. Write-Ahead Log (WAL)

Concept

Before any write touches the MemTable, it is durably appended to the WAL file. On crash, the WAL is replayed to reconstruct the MemTable. Each record is wrapped in an 8-byte header that contains the payload length and a CRC-32 checksum. A truncated final record (the only one that can be partially written on crash) is silently dropped.

┌─────────────────────────────────────────────┐
│  4 bytes: payload length (little-endian)    │
│  4 bytes: CRC-32 of payload (IEEE)          │
│  N bytes: payload                           │
└─────────────────────────────────────────────┘

Go implementation (`lab01/wal.go`)

const headerSize = 8  // 4B len + 4B crc32

type WAL struct{ f *os.File }

func (w *WAL) Append(data []byte) error {
    var hdr [headerSize]byte
    binary.LittleEndian.PutUint32(hdr[0:4], uint32(len(data)))
    binary.LittleEndian.PutUint32(hdr[4:8], crc32.ChecksumIEEE(data))
    if _, err := w.f.Write(hdr[:]); err != nil { return err }
    if _, err := w.f.Write(data);   err != nil { return err }
    return w.f.Sync()   // fdatasync: flush OS buffer to durable storage
}

func Recover(path string) ([][]byte, error) {
    // Reads [hdr | data] records; verifies CRC; stops on truncated/corrupt.
    // Returns (nil, nil) if the file does not exist.
}

Python implementation

import os, struct, zlib

HEADER_SIZE = 8  # 4B length + 4B CRC32

class WAL:
    def __init__(self, path: str, mode: str = 'ab'):
        self._f = open(path, mode)

    def append(self, data: bytes):
        crc    = zlib.crc32(data) & 0xFFFFFFFF
        header = struct.pack('<II', len(data), crc)
        self._f.write(header + data)
        self._f.flush()
        os.fsync(self._f.fileno())   # durability guarantee

    def close(self):
        self._f.close()

    @staticmethod
    def recover(path: str) -> list[bytes]:
        records = []
        if not os.path.exists(path):
            return records
        with open(path, 'rb') as f:
            while True:
                hdr = f.read(HEADER_SIZE)
                if len(hdr) < HEADER_SIZE:
                    break
                length, stored_crc = struct.unpack('<II', hdr)
                data = f.read(length)
                if len(data) < length:
                    break
                if (zlib.crc32(data) & 0xFFFFFFFF) != stored_crc:
                    break
                records.append(data)
        return records

Example: write three records, inspect bytes, recover

import tempfile

path = tempfile.mktemp(suffix='.wal')
wal = WAL(path, mode='wb')
payloads = [b"age\x0025", b"city\x00London", b"name\x00Alice"]
for p in payloads:
    wal.append(p)
wal.close()

# Inspect raw bytes on disk:
with open(path, 'rb') as f:
    raw = f.read()
offset = 0
while offset < len(raw):
    length, crc = struct.unpack('<II', raw[offset:offset+8])
    data = raw[offset+8 : offset+8+length]
    print(f"  len={length:3d}  crc={crc:#010x}  payload={data}")
    offset += 8 + length

  len=  7  crc=0x...  payload=b'age\x0025'
  len= 11  crc=0x...  payload=b'city\x00London'
  len= 10  crc=0x...  payload=b'name\x00Alice'

# Crash recovery:
recovered = WAL.recover(path)
for rec in recovered:
    key, _, val = rec.partition(b'\x00')
    print(f"  {key.decode()} = {val.decode()}")
# age = 25
# city = London
# name = Alice

In real database engines

PostgreSQL (src/backend/access/transam/xlog.c, pg_wal/) Postgres calls its WAL the Write-Ahead Log (same name). Key differences from LevelDB’s WAL:

8 KiB pages inside 16 MiB segment files (000000010000000000000001, …)
Each page has a XLogPageHeaderData (magic + TLI + LSN)
Records are typed: XLOG_HEAP_INSERT, XLOG_HEAP_UPDATE, XLOG_BTREE_SPLIT_L, etc.
Group commit: multiple transactions’ WAL records are written in one pg_pwrite() call, then fsync() once for the whole group
Crash recovery in StartupXLOG() replays from the last checkpoint LSN
Replication streams the same WAL bytes to standbys (physical replication) or decoded change records (logical replication via pg_logical)

InnoDB (storage/innobase/log/, ib_logfile0) InnoDB’s redo log is a circular ring buffer on disk:

Fixed total size (default 48 MiB, configurable up to 512 GiB in MySQL 8.0)
Write position = Log.lsn; checkpoint position = Log.last_checkpoint_lsn
Records called mlog entries: MLOG_1BYTE, MLOG_REC_INSERT, MLOG_PAGE_CREATE, …
A mini-transaction (mtr_t) buffers redo records in memory, then commits them atomically to the log buffer with a spin lock
fsync() is called on commit (or deferred with innodb_flush_log_at_trx_commit=2 for performance)

SQLite WAL mode (src/wal.c) SQLite’s WAL is unusual: it is a shadow copy log, not a redo log.

Readers read from the WAL first (newest version wins), then the main database file
The WAL index (-shm file, shared memory) maps page numbers to WAL frame positions
Checkpointing copies WAL frames back to the main database file, then resets the WAL
This design allows concurrent readers and one writer with no read-lock contention

Apache Kafka (commit log as primary data structure) Kafka’s partition is only an append-only log — there is no separate WAL because the log IS the data. Each segment is a pair of files:

.log — binary records (offset + size + CRC + payload), same framing as our WAL
.index — sparse index mapping logical offset → file offset (same idea as SSTable index)
.timeindex — sparse timestamp → offset index

Producers write to the active segment; consumers read at arbitrary offsets. Retention by time or size deletes old segments — no compaction needed for the log itself (unless log compaction is enabled, which is then K-way merge).

Key design lesson: the WAL’s framing (length + checksum + payload) is universal. Every durable system — from a toy key-value store to PostgreSQL to Kafka — converges on this format because it is the minimum structure needed to detect a torn write and replay clean records after a crash.

5. SSTable (Sorted String Table)

Concept

When the MemTable is flushed to disk it becomes an immutable SSTable file. Keys are written in sorted order. A compact in-memory index (one entry per record, stored at the end of the file) enables O(log n) point lookup.

File layout:

┌─────────────────────────────┐
│  data record 0              │  varint(keyLen) | key | varint(valLen) | val
│  data record 1              │
│  ...                        │
├─────────────────────────────┤  <- indexOffset
│  index record 0             │  varint(keyLen) | key | 8B LE data offset
│  index record 1             │
│  ...                        │
├─────────────────────────────┤
│  8B indexOffset (LE)        │  footer
│  8B magic = 0x1edb4b4f      │
└─────────────────────────────┘

Varint encoding saves space for small values. Each byte stores 7 bits of payload; the MSB signals “more bytes follow”:

value   1 → 0x01           (1 byte)
value 128 → 0x80 0x01      (2 bytes)
value 300 → 0xAC 0x02      (2 bytes): 300 = 0b100101100
                                       low 7 bits = 0x2C | 0x80 = 0xAC
                                       next 7 bits = 0x02

Go implementation (`lab04/sstable.go`)

func appendVarint(buf []byte, v uint64) []byte {
    for v >= 0x80 {
        buf = append(buf, byte(v)|0x80)  // low 7 bits + continuation bit
        v >>= 7
    }
    return append(buf, byte(v))
}

type Builder struct {
    f          *os.File
    index      []indexEntry  // (key, offset) per record
    dataOffset int64
}

func (b *Builder) Add(key, value []byte) error {
    offset := b.dataOffset
    var buf []byte
    buf = appendVarint(buf, uint64(len(key)))
    buf = append(buf, key...)
    buf = appendVarint(buf, uint64(len(value)))
    buf = append(buf, value...)
    n, err := b.f.Write(buf)
    b.dataOffset += int64(n)
    b.index = append(b.index, indexEntry{lastKey: key, offset: uint64(offset)})
    return err
}

func (b *Builder) Finish() error {
    indexOffset := b.dataOffset
    for _, e := range b.index {
        var buf []byte
        buf = appendVarint(buf, uint64(len(e.lastKey)))
        buf = append(buf, e.lastKey...)
        var off [8]byte
        binary.LittleEndian.PutUint64(off[:], e.offset)
        buf = append(buf, off[:]...)
        b.f.Write(buf)
    }
    var footer [16]byte
    binary.LittleEndian.PutUint64(footer[0:8], uint64(indexOffset))
    binary.LittleEndian.PutUint64(footer[8:16], magic)  // 0x1edb4b4f
    b.f.Write(footer[:])
    return b.f.Sync()
}

Python implementation

import struct, os

MAGIC = 0x1EDB4B4F

def encode_varint(v: int) -> bytes:
    out = bytearray()
    while v >= 0x80:
        out.append((v & 0x7F) | 0x80)
        v >>= 7
    out.append(v)
    return bytes(out)

def decode_varint(data: bytes, offset: int) -> tuple[int, int]:
    """Returns (value, new_offset)."""
    v, shift = 0, 0
    while True:
        b = data[offset]; offset += 1
        v |= (b & 0x7F) << shift
        if not (b & 0x80):
            return v, offset
        shift += 7

class SSTBuilder:
    def __init__(self, path: str):
        self._f      = open(path, 'wb')
        self._index  = []   # [(key_bytes, file_offset)]
        self._offset = 0

    def add(self, key: bytes, value: bytes):
        offset = self._offset
        rec  = encode_varint(len(key))   + key
        rec += encode_varint(len(value)) + value
        self._f.write(rec)
        self._offset += len(rec)
        self._index.append((key, offset))

    def finish(self):
        index_offset = self._offset
        for key, off in self._index:
            rec = encode_varint(len(key)) + key + struct.pack('<Q', off)
            self._f.write(rec)
        self._f.write(struct.pack('<QQ', index_offset, MAGIC))
        self._f.flush(); os.fsync(self._f.fileno()); self._f.close()


class SSTReader:
    def __init__(self, path: str):
        with open(path, 'rb') as f:
            self._data = f.read()
        index_offset, magic_val = struct.unpack('<QQ', self._data[-16:])
        assert magic_val == MAGIC
        self._index = []
        pos = index_offset
        while pos < len(self._data) - 16:
            klen, pos = decode_varint(self._data, pos)
            key = self._data[pos:pos+klen]; pos += klen
            off = struct.unpack('<Q', self._data[pos:pos+8])[0]; pos += 8
            self._index.append((key, off))

    def get(self, key: bytes, read_seq: int) -> Optional[bytes]:
        seek = encode_internal_key(key, read_seq, TYPE_VALUE)
        lo, hi = 0, len(self._index)
        while lo < hi:
            mid = (lo + hi) // 2
            if compare_internal(self._index[mid][0], seek) < 0:
                lo = mid + 1
            else:
                hi = mid
        for i in range(lo, len(self._index)):
            ik, val = self._read_record(self._index[i][1])
            uk, seq, kt = decode_internal_key(ik)
            if uk != key: break
            if seq > read_seq: continue
            if kt == TYPE_DELETE: return None
            return val
        return None

    def _read_record(self, offset: int) -> tuple[bytes, bytes]:
        klen, p = decode_varint(self._data, offset)
        key = self._data[p:p+klen]; p += klen
        vlen, p = decode_varint(self._data, p)
        return key, self._data[p:p+vlen]

    def __iter__(self):
        index_offset = struct.unpack('<Q', self._data[-16:-8])[0]
        pos = 0
        while pos < index_offset:
            klen, p = decode_varint(self._data, pos)
            key = self._data[p:p+klen]; p += klen
            vlen, p = decode_varint(self._data, p)
            val = self._data[p:p+vlen]; p += vlen
            yield key, val
            pos = p

Example: flush MemTable → SSTable → point lookup

import tempfile

entries = [
    (encode_internal_key(b"age",  1, TYPE_VALUE), b"25"),
    (encode_internal_key(b"city", 2, TYPE_VALUE), b"London"),
    (encode_internal_key(b"name", 3, TYPE_VALUE), b"Alice"),
]

sst_path = tempfile.mktemp(suffix='.sst')
bld = SSTBuilder(sst_path)
for ik, val in entries:
    bld.add(ik, val)
bld.finish()

print(f"SSTable size: {os.path.getsize(sst_path)} bytes")

rdr = SSTReader(sst_path)
print(rdr.get(b"name", 3))   # b'Alice'
print(rdr.get(b"city", 2))   # b'London'
print(rdr.get(b"age",  0))   # None — readSeq=0 predates all writes

for ik, val in rdr:
    uk, seq, kt = decode_internal_key(ik)
    print(f"  {uk.decode():8s} seq={seq}  ->  {val.decode()}")

Output:

SSTable size: 87 bytes
b'Alice'
b'London'
None
  age      seq=1  ->  25
  city     seq=2  ->  London
  name     seq=3  ->  Alice

In real database engines

LevelDB (table/table.cc, table/block.cc) An LevelDB SSTable has four block types:

Data blocks — 4 KiB blocks of prefix-compressed sorted records
Filter block — optional Bloom filter (one filter per 2 KiB of data)
Metaindex block — maps filter block name → its offset
Index block — one entry per data block: (last_key_in_block → BlockHandle{offset, size})

The footer is 48 bytes: metaindex_handle + index_handle + padding + magic (0xdb4775248b80fb57). This two-level index (index block → data block) means a point lookup costs two block reads: one to find the right data block, one to read it.

RocksDB (table/block_based/, table/block_based_table_builder.cc) RocksDB’s BlockBasedTable extends LevelDB’s format:

Partitioned index/filters — index and filter blocks are themselves split into smaller sub-blocks, enabling partial caching
Block cache — LRU or Clock cache; blocks are decompressed on read and cached in the block cache, not the OS page cache
Column families — each CF has its own set of SSTables; a single DB can have multiple independent LSM trees sharing one WAL
Ingestion — IngestExternalFile() links a pre-built SSTable directly into the LSM tree without going through MemTable or compaction

Apache Cassandra (org.apache.cassandra.io.sstable) Cassandra’s SSTable format has evolved across versions (ka/la/ma/mc/md/me). Key additions over LevelDB:

Partition index — two-level: a summary (in RAM) + partition index on disk
Column index — for wide rows, an additional index within a partition
Bloom filter — per-SSTable, checked before any disk read
Statistics — min/max column values, tombstone counts, estimated cardinality — used by the query planner to skip SSTables

Apache Parquet (columnar SSTable format) Parquet stores data column by column instead of row by row. Layout:

Row group 0:
  Column chunk: age    [page0][page1]...   <- only age values, compressed
  Column chunk: city   [page0][page1]...
  Column chunk: name   [page0][page1]...
Row group 1: ...
Footer: schema + row group metadata + column statistics
Magic: PAR1

A query SELECT age WHERE city = 'London' reads only the city and age column chunks, skipping name entirely — predicate pushdown at the storage layer. DuckDB, Apache Spark, Delta Lake, and Apache Iceberg all use Parquet as their on-disk SSTable format.

Key design lesson: the SSTable is the universal unit of immutable sorted storage. Every LSM-family system — LevelDB, RocksDB, Cassandra, HBase, Badger — converges on the same structure: sorted records + sparse index + Bloom filter + footer with index offset. The only variation is whether records are row-oriented or column-oriented.

6. Min-Heap (K-way Merge)

Concept

Compaction reads K sorted input iterators (L0 SSTables + L1 SSTables) and produces one merged sorted output. A min-heap always contains the current (smallest remaining) element of each iterator. Each pop+advance costs O(log K), giving O(N log K) total for N records across K sources.

Initial heap (3 inputs):
  Input A: age/1  city/7  name/3
  Input B: city/2  name/1
  Input C: city/6

Step 1: pop min = age/1     -> advance A  -> emit age=25
        heap: {city/7, city/2, city/6}

Step 2: pop min = city/7    -> advance A  -> emit city=Paris (newest)
        heap: {name/3, city/2, city/6}

Step 3: pop min = city/6    -> advance C  -> SKIP (same user-key "city", already emitted)
        heap: {name/3, city/2}

Step 4: pop min = city/2    -> advance B  -> SKIP (same user-key "city")
        heap: {name/3, name/1}

Step 5: pop min = name/3    -> advance A  -> emit name=Bob (newest)
        heap: {name/1}

Step 6: pop min = name/1    -> advance B  -> SKIP (same user-key "name")
        heap: {}  -> done

Go implementation (`lab06/iter.go`)

type heapNode struct {
    src   rawIter
    key   []byte
    value []byte
}

type nodeHeap []heapNode

func (h nodeHeap) Len() int      { return len(h) }
func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h nodeHeap) Less(i, j int) bool {
    return lab02.CompareInternal(h[i].key, h[j].key) < 0
}
func (h *nodeHeap) Push(x interface{}) { *h = append(*h, x.(heapNode)) }
func (h *nodeHeap) Pop() interface{} {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

func (m *MergedIterator) next() {
    for {
        if m.h.Len() == 0 { m.valid = false; return }
        top := heap.Pop(&m.h).(heapNode)

        // Push the source's next element back into the heap.
        top.src.Next()
        if top.src.Valid() {
            heap.Push(&m.h, heapNode{
                src: top.src, key: top.src.Key(), value: top.src.Value(),
            })
        }

        uk, seq, kt := lab02.DecodeInternalKey(top.key)
        if seq > m.readSeq          { continue }  // future write
        if bytes.Equal(uk, m.lastUserKey) { continue }  // older dup
        m.lastUserKey = uk
        if kt == lab02.TypeDelete   { continue }  // tombstone

        m.key, m.value, m.valid = top.key, top.value, true
        return
    }
}

Python implementation

import heapq

class _HeapEntry:
    """Comparable wrapper so heapq orders by CompareInternal."""
    __slots__ = ('key', 'val', 'src')
    def __init__(self, key, val, src): self.key=key; self.val=val; self.src=src
    def __lt__(self, o): return compare_internal(self.key, o.key) < 0
    def __eq__(self, o): return compare_internal(self.key, o.key) == 0

class MergedIterator:
    """K-way merge with MVCC dedup and tombstone suppression."""
    def __init__(self, sources: list, read_seq: int = 2**64 - 1):
        self._read_seq = read_seq
        self._heap: list = []
        for src in sources:
            it = iter(src)
            try:
                ik, val = next(it)
                heapq.heappush(self._heap, _HeapEntry(ik, val, it))
            except StopIteration:
                pass

    def __iter__(self):
        last_user_key: Optional[bytes] = None
        while self._heap:
            entry = heapq.heappop(self._heap)
            try:
                nik, nval = next(entry.src)
                heapq.heappush(self._heap, _HeapEntry(nik, nval, entry.src))
            except StopIteration:
                pass

            uk, seq, kt = decode_internal_key(entry.key)
            if seq > self._read_seq: continue       # future version
            if uk == last_user_key:  continue       # older dup
            last_user_key = uk
            if kt == TYPE_DELETE:    continue       # tombstone
            yield entry.key, entry.val

Example: compact three SSTables into one merged output

import tempfile

def make_sst(path, pairs):
    """pairs = [(user_key_str, seq, key_type, value_str)]"""
    sorted_pairs = sorted(pairs,
        key=lambda x: encode_internal_key(x[0].encode(), x[1], x[2]))
    bld = SSTBuilder(path)
    for uk, seq, kt, val in sorted_pairs:
        bld.add(encode_internal_key(uk.encode(), seq, kt), val.encode())
    bld.finish()

# L0 SSTable 0: newest writes
sst0 = tempfile.mktemp(suffix='.sst')
make_sst(sst0, [("city", 7, TYPE_VALUE, "Paris"), ("name", 5, TYPE_VALUE, "Bob")])

# L0 SSTable 1: earlier writes
sst1 = tempfile.mktemp(suffix='.sst')
make_sst(sst1, [("age", 1, TYPE_VALUE, "25"), ("city", 2, TYPE_VALUE, "London")])

# L1 SSTable: old data
sst2 = tempfile.mktemp(suffix='.sst')
make_sst(sst2, [("city", 6, TYPE_VALUE, "Berlin"), ("name", 3, TYPE_VALUE, "Alice")])

readers = [SSTReader(p) for p in [sst0, sst1, sst2]]
mi = MergedIterator(readers, read_seq=10)

print("Merged output (one entry per user-key, newest wins):")
for ik, val in mi:
    uk, seq, kt = decode_internal_key(ik)
    print(f"  {uk.decode():8s} seq={seq}  ->  {val.decode()}")

Output:

Merged output (one entry per user-key, newest wins):
  age      seq=1  ->  25
  city     seq=7  ->  Paris    <- seq=6 and seq=2 deduplicated
  name     seq=5  ->  Bob      <- seq=3 deduplicated

This output is exactly what the new L1 SSTable contains after compaction.

In real database engines

LevelDB (db/version_set.cc, table/merger.cc) MergingIterator wraps a MergeIterHeap (std::priority_queue) over all child iterators. Compaction in DoCompactionWork() calls input->key() / input->Next() in a loop — exactly the pattern above. The dedup logic checks ikey.user_key == last_key and drops the older version. kTypeDeletion entries are dropped only when all levels below the current compaction level are empty (otherwise a delete could expose an older version).

RocksDB (table/merging_iterator.cc) RocksDB uses a binary heap (same as above) but adds:

pinned_iters_mgr — iterators can pin blocks in the block cache to avoid eviction while compaction is running
CompactionIterator (db/compaction/compaction_iterator.cc) — separate class that handles merge operators, range tombstones (FragmentedRangeTombstoneIterator), and TTL expiry on top of the raw K-way merge

PostgreSQL external merge sort (src/backend/utils/sort/tuplesort.c) Postgres uses the same K-way merge for ORDER BY and index builds:

Run formation — fill memory with tuples, sort in RAM (quicksort)
Merge — LogicalTapeSet creates K sorted runs on disk; a replacement selection heap merges them into one output tape The heap holds the current minimum tuple from each tape, same structure as our nodeHeap.

Apache Spark (core/src/main/scala/org/apache/spark/util/collection/ExternalSorter.scala) Spill files are individual sorted runs. At merge time Spark opens one iterator per spill file and feeds them into a priority queue — identical to our Python MergedIterator. The merged stream is written as the final RDD partition or shuffle output file.

Apache Cassandra compaction strategies All three compaction strategies ultimately perform K-way merge but differ in which SSTables to merge:

STCS (Size-Tiered): merge SSTables of similar size — fewest merges, highest space amp
LCS (Leveled): merge one SSTable from L_n into overlapping SSTables in L_{n+1} — same algorithm as LevelDB
TWCS (Time-Window): merge SSTables within a time window — optimized for time-series data where old windows are never written again

Key design lesson: the K-way merge heap is the inner loop of every compaction and every external sort. Once you see it here, you recognize it everywhere: database index builds, MapReduce shuffle merge phase, Parquet file merge in Delta Lake OPTIMIZE, PostgreSQL CLUSTER command.

7. Red-Black Tree

Concept

A red-black tree is a self-balancing binary search tree (BST) with one extra bit per node: its color (red or black). Four invariants keep it balanced:

Every node is red or black.
The root is black.
No two adjacent red nodes (a red node’s parent must be black).
Every path from any node to a NIL leaf crosses the same number of black nodes.

These rules guarantee the tree’s height is at most $2\log_2(n+1)$, bounding all operations at O(log n) worst-case — unlike the skip list’s O(log n) expected time.

Insert order: "name", "age", "city"

After inserting "name" (root, forced black):
    [name:B]

After inserting "age" (red, left child):
    [name:B]
    /
  [age:R]

After inserting "city" (red):
  Would make [age:R]→[city:R] — violates rule 3.
  Left-rotate on "age", then right-rotate on "name", recolor:
      [city:B]
      /       \
  [age:R]   [name:R]

LevelDB comparison: LevelDB uses a skip list for its MemTable. A red-black tree is the natural alternative: C++ std::map and Java TreeMap use one; RocksDB optionally replaces the skip list with a hash skip list or could use a BST variant. The key trade-off is concurrency — skip lists are easier to make lock-free via CAS on individual next pointers, while red-black tree rotations touch multiple nodes simultaneously.

Serialization

Red-black trees are always in-memory structures. To persist them:

Option A — sorted flat dump (what LevelDB does):
  In-order traversal → varint-encoded records → identical to SSTable data section.
  Color information is discarded; the tree is rebuilt from scratch on reload.

Option B — structural dump (for debugging / snapshots):
  Per-node record:
  [1B color: 0=black 1=red]
  [8B left  child file offset, 0xFF...FF = NIL]
  [8B right child file offset, 0xFF...FF = NIL]
  [2B keyLen][2B valLen][key bytes][val bytes]
  File header: [8B root offset]

LevelDB takes Option A: the MemTable (skip list, but same idea) is flushed as a sorted SSTable — the in-memory sorted structure is discarded entirely.

Go implementation

type rbColor bool

const (
    rbBlack rbColor = false
    rbRed   rbColor = true
)

type rbNode struct {
    key, value  []byte
    color        rbColor
    left, right, parent *rbNode
}

type RBTree struct {
    root *rbNode
    nil_ *rbNode // sentinel NIL node (always black)
    size int
}

func NewRBTree() *RBTree {
    sentinel := &rbNode{color: rbBlack}
    sentinel.left = sentinel
    sentinel.right = sentinel
    sentinel.parent = sentinel
    return &RBTree{nil_: sentinel, root: sentinel}
}

func (t *RBTree) rotateLeft(x *rbNode) {
    y := x.right
    x.right = y.left
    if y.left != t.nil_ {
        y.left.parent = x
    }
    y.parent = x.parent
    if x.parent == t.nil_ {
        t.root = y
    } else if x == x.parent.left {
        x.parent.left = y
    } else {
        x.parent.right = y
    }
    y.left = x
    x.parent = y
}

func (t *RBTree) rotateRight(x *rbNode) {
    y := x.left
    x.left = y.right
    if y.right != t.nil_ {
        y.right.parent = x
    }
    y.parent = x.parent
    if x.parent == t.nil_ {
        t.root = y
    } else if x == x.parent.right {
        x.parent.right = y
    } else {
        x.parent.left = y
    }
    y.right = x
    x.parent = y
}

func (t *RBTree) Put(key, value []byte) {
    z := &rbNode{
        key: key, value: value, color: rbRed,
        left: t.nil_, right: t.nil_, parent: t.nil_,
    }
    x, y := t.root, t.nil_
    for x != t.nil_ {
        y = x
        c := bytes.Compare(key, x.key)
        if c == 0 {
            x.value = value // update in place
            return
        }
        if c < 0 {
            x = x.left
        } else {
            x = x.right
        }
    }
    z.parent = y
    if y == t.nil_ {
        t.root = z
    } else if bytes.Compare(key, y.key) < 0 {
        y.left = z
    } else {
        y.right = z
    }
    t.fixInsert(z)
    t.size++
}

func (t *RBTree) fixInsert(z *rbNode) {
    for z.parent.color == rbRed {
        if z.parent == z.parent.parent.left {
            y := z.parent.parent.right
            if y.color == rbRed { // Case 1: uncle red — recolor
                z.parent.color = rbBlack
                y.color = rbBlack
                z.parent.parent.color = rbRed
                z = z.parent.parent
            } else {
                if z == z.parent.right { // Case 2: uncle black, z is right child
                    z = z.parent
                    t.rotateLeft(z)
                }
                z.parent.color = rbBlack // Case 3: uncle black, z is left child
                z.parent.parent.color = rbRed
                t.rotateRight(z.parent.parent)
            }
        } else {
            y := z.parent.parent.left
            if y.color == rbRed {
                z.parent.color = rbBlack
                y.color = rbBlack
                z.parent.parent.color = rbRed
                z = z.parent.parent
            } else {
                if z == z.parent.left {
                    z = z.parent
                    t.rotateRight(z)
                }
                z.parent.color = rbBlack
                z.parent.parent.color = rbRed
                t.rotateLeft(z.parent.parent)
            }
        }
    }
    t.root.color = rbBlack
}

func (t *RBTree) Get(key []byte) ([]byte, bool) {
    x := t.root
    for x != t.nil_ {
        c := bytes.Compare(key, x.key)
        if c == 0 {
            return x.value, true
        }
        if c < 0 {
            x = x.left
        } else {
            x = x.right
        }
    }
    return nil, false
}

// InOrder yields (key, value) sorted — same iteration contract as SkipList.
func (t *RBTree) InOrder(fn func(key, value []byte)) {
    var walk func(*rbNode)
    walk = func(n *rbNode) {
        if n == t.nil_ {
            return
        }
        walk(n.left)
        fn(n.key, n.value)
        walk(n.right)
    }
    walk(t.root)
}

// Serialize writes the sorted flat record format — identical to SSTable data section.
func (t *RBTree) Serialize(w io.Writer) error {
    var err error
    t.InOrder(func(key, value []byte) {
        if err != nil {
            return
        }
        var buf []byte
        buf = appendVarint(buf, uint64(len(key)))
        buf = append(buf, key...)
        buf = appendVarint(buf, uint64(len(value)))
        buf = append(buf, value...)
        _, err = w.Write(buf)
    })
    return err
}

Python implementation

BLACK, RED = False, True

class _RBNode:
    __slots__ = ('key', 'value', 'color', 'left', 'right', 'parent')
    def __init__(self, key, value, color, nil):
        self.key = key; self.value = value; self.color = color
        self.left = self.right = self.parent = nil

class RBTree:
    """Self-balancing BST with O(log n) worst-case insert/lookup."""

    def __init__(self):
        self._nil  = _RBNode(b'', b'', BLACK, None)
        self._nil.left = self._nil.right = self._nil.parent = self._nil
        self._root = self._nil

    def _rotate_left(self, x):
        y = x.right; x.right = y.left
        if y.left is not self._nil: y.left.parent = x
        y.parent = x.parent
        if   x.parent is self._nil:    self._root     = y
        elif x is x.parent.left:       x.parent.left  = y
        else:                          x.parent.right = y
        y.left = x; x.parent = y

    def _rotate_right(self, x):
        y = x.left; x.left = y.right
        if y.right is not self._nil: y.right.parent = x
        y.parent = x.parent
        if   x.parent is self._nil:    self._root     = y
        elif x is x.parent.right:      x.parent.right = y
        else:                          x.parent.left  = y
        y.right = x; x.parent = y

    def put(self, key: bytes, value: bytes):
        z = _RBNode(key, value, RED, self._nil)
        y, x = self._nil, self._root
        while x is not self._nil:
            y = x
            if key == x.key: x.value = value; return
            x = x.left if key < x.key else x.right
        z.parent = y
        if   y is self._nil:   self._root = z
        elif key < y.key:      y.left  = z
        else:                  y.right = z
        self._fix_insert(z)

    def _fix_insert(self, z):
        while z.parent.color == RED:
            if z.parent is z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == RED:                          # Case 1
                    z.parent.color = BLACK; y.color = BLACK
                    z.parent.parent.color = RED; z = z.parent.parent
                else:
                    if z is z.parent.right:                 # Case 2
                        z = z.parent; self._rotate_left(z)
                    z.parent.color = BLACK                  # Case 3
                    z.parent.parent.color = RED
                    self._rotate_right(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == RED:
                    z.parent.color = BLACK; y.color = BLACK
                    z.parent.parent.color = RED; z = z.parent.parent
                else:
                    if z is z.parent.left:
                        z = z.parent; self._rotate_right(z)
                    z.parent.color = BLACK
                    z.parent.parent.color = RED
                    self._rotate_left(z.parent.parent)
        self._root.color = BLACK

    def get(self, key: bytes) -> Optional[bytes]:
        x = self._root
        while x is not self._nil:
            if key == x.key: return x.value
            x = x.left if key < x.key else x.right
        return None

    def __iter__(self):
        """In-order traversal — sorted, same contract as SkipList.__iter__."""
        stack, cur = [], self._root
        while stack or cur is not self._nil:
            while cur is not self._nil:
                stack.append(cur); cur = cur.left
            cur = stack.pop()
            yield cur.key, cur.value
            cur = cur.right

    def serialize(self) -> bytes:
        """Flat in-order varint record format — same layout as SSTable data section."""
        out = bytearray()
        for key, val in self:
            out += encode_varint(len(key)) + key
            out += encode_varint(len(val))  + val
        return bytes(out)

Example: insert age/city/name, verify sort order, serialize

rbt = RBTree()
# Insert deliberately out of alphabetical order
rbt.put(encode_internal_key(b"name", 3, TYPE_VALUE), b"Alice")
rbt.put(encode_internal_key(b"age",  1, TYPE_VALUE), b"25")
rbt.put(encode_internal_key(b"city", 2, TYPE_VALUE), b"London")

print("In-order (identical result to SkipList):")
for ik, val in rbt:
    uk, seq, kt = decode_internal_key(ik)
    print(f"  {uk.decode():8s} seq={seq}  ->  {val.decode()}")

blob = rbt.serialize()
print(f"\nSerialized {len(blob)} bytes — same layout as SSTable data section")

# Verify: the serialized bytes are identical to SSTBuilder output
# for the same three records written in the same order.

Output:

In-order (identical result to SkipList):
  age      seq=1  ->  25
  city     seq=2  ->  London
  name     seq=3  ->  Alice

Serialized 49 bytes — same layout as SSTable data section

Skip List vs Red-Black Tree

	Skip List (`lab02`)	Red-Black Tree
Insert complexity	O(log n) expected	O(log n) worst-case
Memory per node	~3 pointers avg (level 1–2 typical)	3 child/parent pointers + sentinel
Lock-free	Yes — CAS on `next` pointers	Hard — rotations touch 3+ nodes
Cache locality	Poor (pointer chasing)	Poor (same)
Serialization	In-order scan	In-order traversal
Used by	LevelDB, RocksDB MemTable	`std::map`, Java `TreeMap`, Linux rbtree

In real database engines

Linux kernel (include/linux/rbtree.h, lib/rbtree.c) The kernel ships a generic red-black tree used in dozens of subsystems:

Subsystem	What is keyed	Source file
CFS scheduler	task `vruntime` (CPU fairness)	`kernel/sched/fair.c`
Virtual memory	`vm_area_struct` (VMA) regions	`mm/mmap.c`
epoll	file descriptor + interest events	`fs/eventpoll.c`
Ext4 extents	block range → physical block	`fs/ext4/extents.c`
Pipe inodes	inode number	`fs/pipe.c`

The kernel’s rb_node embeds directly inside the data structure (no separate allocation), accessed via container_of(). Colors are stored in the LSB of the rb_parent_color pointer — exploiting the fact that pointers are always 4-byte aligned, making the LSB always zero except for the color bit.

struct rb_node {
    unsigned long __rb_parent_color; // parent ptr | color in bit 0
    struct rb_node *rb_right;
    struct rb_node *rb_left;
};

glibc malloc (malloc/malloc.c) Free chunks larger than FASTBIN_CONSOLIDATION_THRESHOLD (~64 KiB) are tracked in a red-black tree keyed by chunk size. malloc(n) does a rb_find_first_fit(size) — O(log n) — to find the smallest chunk ≥ n. Smaller free chunks use segregated free lists (bins) indexed by size class, which is why a benchmark allocating many same-sized objects is faster than allocating varied sizes.

Java TreeMap / TreeSet (JDK java/util/TreeMap.java) Java’s TreeMap is a textbook red-black tree. RocksDB’s Java API uses a TreeMap<InternalKey, byte[]> in some of its in-memory test stubs, and Cassandra’s ConcurrentSkipListMap is the production alternative that trades worst-case guarantees for better concurrent scalability.

Nginx timer wheel (src/event/ngx_event_timer.c) Nginx stores all pending I/O timeouts in a red-black tree keyed by expiry time (milliseconds). ngx_event_find_timer() peeks at the leftmost node (minimum expiry) in O(1); ngx_event_expire_timers() pops expired events in order. This is functionally identical to a priority queue but with O(log n) cancellation (removing an arbitrary node) instead of O(n).

Key design lesson: the red-black tree is the kernel/systems programmer’s choice whenever you need a sorted container with O(log n) worst-case and the ability to delete an arbitrary node by pointer (not just the minimum). A heap gives you O(1) find-min but O(n) arbitrary delete; a skip list gives you O(log n) expected but poor cache behavior; only the red-black tree gives O(log n) worst-case insert + delete + arbitrary-key lookup with compact memory (3 pointers + 1 bit per node).

8. B-Tree

Concept

A B-tree of order m is a balanced m-way search tree where:

Every non-root node holds between ⌈m/2⌉ and m−1 keys.
An internal node with k keys has k+1 children.
All leaves are at the same depth.
Both internal nodes and leaves store values — a search can terminate at any level.

B-tree (order 3, max 2 keys/node) after inserting age, city, name:

         ┌──────────────┐
         │ "city"="Lon" │   ← value lives right here in the internal node
         └──────────────┘
        /                \
┌──────────────┐   ┌──────────────┐
│ "age" = "25" │   │"name"="Alice"│
└──────────────┘   └──────────────┘

Relation to this repo: The option-a-sqlite and option-b-sqlite labs use SQLite as their backend. SQLite stores every table row in a B-tree page — sqlite3BtreeInsert encodes the row as a cell and inserts it into the appropriate node, potentially splitting pages.

B-Tree vs LSM trade-offs:

	B-Tree (SQLite backend)	LSM Tree (LevelDB)
Read	O(log n), warm page cache	O(levels × log n)
Write	Random I/O — update in place	Sequential I/O — append-only
Write amplification	~2–3×	~10–30×
Space amplification	Low (no stale versions)	Medium (until compaction)
Crash safety	Page journaling or WAL	WAL + immutable SSTables

Serialization: fixed-size pages

Each B-tree node maps to one page (typically 4096 bytes):

Leaf page:
  [1B: type = 0x02]
  [2B: numKeys, little-endian]
  per record: [2B keyLen][2B valLen][key bytes][val bytes]

Internal page:
  [1B: type = 0x01]
  [2B: numKeys]
  per key:    [2B keyLen][2B valLen][key bytes][val bytes]  ← value stored here too
  per child:  [8B child page ID, little-endian]            ← numKeys+1 entries

File header (page 0):
  [8B magic = 0xB77EEB77EEB77EEB]
  [8B root page ID]
  [8B total page count]

Go implementation

const (
    btOrder    = 3        // max keys per node = 2*btOrder - 1 = 5
    btPageSize = 4096
    btMagic    = uint64(0xB77EEB77EEB77EEB)
    btLeaf     = byte(0x02)
    btInternal = byte(0x01)
)

type btNode struct {
    keys     [][]byte
    values   [][]byte   // parallel to keys in both leaf and internal nodes
    children []*btNode  // len = len(keys)+1 for internal; nil for leaf
    isLeaf   bool
}

type BTree struct{ root *btNode }

func NewBTree() *BTree { return &BTree{root: &btNode{isLeaf: true}} }

func (t *BTree) Get(key []byte) ([]byte, bool) {
    return t.search(t.root, key)
}

func (t *BTree) search(n *btNode, key []byte) ([]byte, bool) {
    i := 0
    for i < len(n.keys) && bytes.Compare(key, n.keys[i]) > 0 {
        i++
    }
    if i < len(n.keys) && bytes.Equal(key, n.keys[i]) {
        return n.values[i], true // found at this node (leaf or internal)
    }
    if n.isLeaf {
        return nil, false
    }
    return t.search(n.children[i], key)
}

func (t *BTree) Put(key, value []byte) {
    root := t.root
    if len(root.keys) == 2*btOrder-1 {
        newRoot := &btNode{isLeaf: false, children: []*btNode{root}}
        t.splitChild(newRoot, 0)
        t.root = newRoot
        t.insertNonFull(newRoot, key, value)
    } else {
        t.insertNonFull(root, key, value)
    }
}

func (t *BTree) insertNonFull(n *btNode, key, value []byte) {
    i := len(n.keys) - 1
    if n.isLeaf {
        n.keys   = append(n.keys,   nil)
        n.values = append(n.values, nil)
        for i >= 0 && bytes.Compare(key, n.keys[i]) < 0 {
            n.keys[i+1]   = n.keys[i]
            n.values[i+1] = n.values[i]
            i--
        }
        // Update existing key
        if i >= 0 && bytes.Equal(key, n.keys[i]) {
            n.values[i] = value
            n.keys   = n.keys[:len(n.keys)-1]
            n.values = n.values[:len(n.values)-1]
            return
        }
        n.keys[i+1]   = key
        n.values[i+1] = value
    } else {
        for i >= 0 && bytes.Compare(key, n.keys[i]) < 0 {
            i--
        }
        i++
        if len(n.children[i].keys) == 2*btOrder-1 {
            t.splitChild(n, i)
            if bytes.Compare(key, n.keys[i]) > 0 {
                i++
            }
        }
        t.insertNonFull(n.children[i], key, value)
    }
}

func (t *BTree) splitChild(parent *btNode, i int) {
    mid   := btOrder - 1
    child := parent.children[i]
    sib   := &btNode{isLeaf: child.isLeaf}
    sib.keys   = append(sib.keys,   child.keys[mid+1:]...)
    sib.values = append(sib.values, child.values[mid+1:]...)
    if !child.isLeaf {
        sib.children = append(sib.children, child.children[mid+1:]...)
        child.children = child.children[:mid+1]
    }
    // Promote median key to parent
    parent.keys   = append(parent.keys,   nil)
    parent.values = append(parent.values, nil)
    parent.children = append(parent.children, nil)
    copy(parent.keys[i+1:],      parent.keys[i:])
    copy(parent.values[i+1:],    parent.values[i:])
    copy(parent.children[i+2:],  parent.children[i+1:])
    parent.keys[i]      = child.keys[mid]
    parent.values[i]    = child.values[mid]
    parent.children[i+1] = sib
    child.keys   = child.keys[:mid]
    child.values = child.values[:mid]
}

// InOrder yields (key, value) sorted — visits internal nodes too.
func (t *BTree) InOrder(fn func(k, v []byte)) { btInOrder(t.root, fn) }

func btInOrder(n *btNode, fn func(k, v []byte)) {
    if n.isLeaf {
        for i, k := range n.keys { fn(k, n.values[i]) }
        return
    }
    for i, k := range n.keys {
        btInOrder(n.children[i], fn)
        fn(k, n.values[i])
    }
    btInOrder(n.children[len(n.keys)], fn)
}

// SerializePage encodes one node into a btPageSize-byte buffer.
func (t *BTree) SerializePage(n *btNode) []byte {
    page := make([]byte, btPageSize)
    if n.isLeaf { page[0] = btLeaf } else { page[0] = btInternal }
    binary.LittleEndian.PutUint16(page[1:3], uint16(len(n.keys)))
    off := 3
    for idx, k := range n.keys {
        binary.LittleEndian.PutUint16(page[off:], uint16(len(k))); off += 2
        copy(page[off:], k); off += len(k)
        v := n.values[idx]
        binary.LittleEndian.PutUint16(page[off:], uint16(len(v))); off += 2
        copy(page[off:], v); off += len(v)
    }
    if !n.isLeaf {
        // child page IDs — in a file-backed tree these are uint64 page numbers
        for range n.children {
            binary.LittleEndian.PutUint64(page[off:], 0 /*placeholder*/); off += 8
        }
    }
    return page
}

Python implementation

BTREE_ORDER = 3        # max keys per node = 2*ORDER - 1 = 5
BTREE_PAGE  = 4096
BTREE_MAGIC = 0xB77EEB77EEB77EEB
BT_LEAF     = 0x02
BT_INTERNAL = 0x01

class _BTNode:
    __slots__ = ('keys', 'values', 'children', 'is_leaf')
    def __init__(self, is_leaf=True):
        self.keys:     list[bytes] = []
        self.values:   list[bytes] = []   # parallel to keys at every level
        self.children: list['_BTNode'] = []
        self.is_leaf   = is_leaf

class BTree:
    """B-tree (order 3): values stored in every node, not just leaves."""

    def __init__(self):
        self._root = _BTNode(is_leaf=True)

    def get(self, key: bytes) -> Optional[bytes]:
        return self._search(self._root, key)

    def _search(self, n: _BTNode, key: bytes) -> Optional[bytes]:
        i = 0
        while i < len(n.keys) and key > n.keys[i]: i += 1
        if i < len(n.keys) and key == n.keys[i]:
            return n.values[i]
        if n.is_leaf: return None
        return self._search(n.children[i], key)

    def put(self, key: bytes, value: bytes):
        root = self._root
        if len(root.keys) == 2 * BTREE_ORDER - 1:
            new_root = _BTNode(is_leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self._root = new_root
        self._insert_non_full(self._root, key, value)

    def _insert_non_full(self, n: _BTNode, key: bytes, value: bytes):
        i = len(n.keys) - 1
        if n.is_leaf:
            n.keys.append(b''); n.values.append(b'')
            while i >= 0 and key < n.keys[i]:
                n.keys[i+1] = n.keys[i]; n.values[i+1] = n.values[i]; i -= 1
            if i >= 0 and key == n.keys[i]:
                n.values[i] = value          # update existing
                n.keys.pop(); n.values.pop()
                return
            n.keys[i+1] = key; n.values[i+1] = value
        else:
            while i >= 0 and key < n.keys[i]: i -= 1
            i += 1
            if len(n.children[i].keys) == 2 * BTREE_ORDER - 1:
                self._split_child(n, i)
                if key > n.keys[i]: i += 1
            self._insert_non_full(n.children[i], key, value)

    def _split_child(self, parent: _BTNode, i: int):
        ORDER  = BTREE_ORDER
        child  = parent.children[i]
        mid    = ORDER - 1
        sib    = _BTNode(is_leaf=child.is_leaf)
        sib.keys   = child.keys[mid+1:]
        sib.values = child.values[mid+1:]
        if not child.is_leaf:
            sib.children   = child.children[ORDER:]
            child.children = child.children[:ORDER]
        parent.keys.insert(i,   child.keys[mid])
        parent.values.insert(i, child.values[mid])
        parent.children.insert(i+1, sib)
        child.keys   = child.keys[:mid]
        child.values = child.values[:mid]

    def __iter__(self):
        """In-order traversal — visits keys in sorted order."""
        yield from self._inorder(self._root)

    def _inorder(self, n: _BTNode):
        if n.is_leaf:
            yield from zip(n.keys, n.values)
        else:
            for i, k in enumerate(n.keys):
                yield from self._inorder(n.children[i])
                yield k, n.values[i]
            yield from self._inorder(n.children[-1])

    def serialize_page(self, n: _BTNode) -> bytes:
        """Fixed 4096-byte page encoding for one B-tree node."""
        buf = bytearray(BTREE_PAGE)
        buf[0] = BT_LEAF if n.is_leaf else BT_INTERNAL
        struct.pack_into('<H', buf, 1, len(n.keys))
        off = 3
        for k, v in zip(n.keys, n.values):
            struct.pack_into('<HH', buf, off, len(k), len(v)); off += 4
            buf[off:off+len(k)] = k; off += len(k)
            buf[off:off+len(v)] = v; off += len(v)
        if not n.is_leaf:
            for _ in n.children:                  # placeholder child page IDs
                struct.pack_into('<Q', buf, off, 0); off += 8
        return bytes(buf)

Example: insert, look up, inspect page bytes

bt = BTree()
bt.put(b"name",  b"Alice")
bt.put(b"age",   b"25")
bt.put(b"city",  b"London")

print("In-order traversal:")
for k, v in bt:
    print(f"  {k.decode():8s} -> {v.decode()}")

print(f"\nRoot is_leaf : {bt._root.is_leaf}")
print(f"Root keys    : {[k.decode() for k in bt._root.keys]}")

page = bt.serialize_page(bt._root)
print(f"\nPage size    : {len(page)} bytes (always fixed)")
print(f"type byte    : {page[0]:#x}  (0x02 = leaf)")
print(f"numKeys      : {struct.unpack_from('<H', page, 1)[0]}")

Output:

In-order traversal:
  age      -> 25
  city     -> London
  name     -> Alice

Root is_leaf : True
Root keys    : ['age', 'city', 'name']

Page size    : 4096 bytes (always fixed)
type byte    : 0x2  (0x02 = leaf)
numKeys      : 3

In real database engines

SQLite (src/btree.c, src/btreeInt.h) Every SQLite table is stored as a B-tree of pages (default 4096 bytes). SQLite distinguishes two page types:

Table B-tree (rowid table) — leaves store the full row payload; internal nodes store only the key (rowid) and child page numbers. This is actually closer to a B+ tree for the data, but SQLite’s source calls it a B-tree because overflow values can chain across pages.
Index B-tree — leaves store the index key + rowid; no separate value column. Used for CREATE INDEX statements.

Page header (first 8–12 bytes of each page):

[1B page type: 0x02=leaf-index 0x05=leaf-table 0x0a=interior-index 0x0d=interior-table]
[2B first freeblock offset]
[2B number of cells on page]
[2B start of cell content area]
[1B fragmented free bytes]
[4B rightmost child page (interior pages only)]

sqlite3BtreeInsert() in btree.c finds the leaf page via moveToChild(), inserts the cell, and calls balance() to split if the page overflows — the same split logic as our _split_child above.

CouchDB (src/couch_btree.erl) CouchDB uses an append-only B-tree: it never overwrites existing pages. Every modification writes new pages at the end of the database file and updates the root pointer in the file header. Old page versions remain until a compaction rewrites the entire file. This gives CouchDB crash safety without a WAL — the file is always consistent at the last committed root pointer — at the cost of unbounded file growth between compactions.

Oracle Index-Organized Tables (IOT) In a regular Oracle table, rows live in a heap file and the B-tree index stores (index_key → rowid → heap lookup) — two I/Os per point lookup. An IOT stores the entire row in the B-tree leaf node, eliminating the second I/O. The primary key is the B-tree key; secondary indexes store the primary key value (not a rowid) as the pointer, making them slightly larger but immune to row movement during reorganization. This is identical to InnoDB’s clustered index design (see B+ Tree section).

Key design lesson: pure B-trees (values in every node) appear in embedded/single-file databases (SQLite, CouchDB) because simplicity matters more than range-scan performance. Once range scans become a first-class workload — which they do in every OLTP system — engines add the leaf linked list and become B+ trees.

9. B+ Tree

Concept

A B+ tree is a B-tree variant with one critical difference:

Internal (routing) nodes store only keys — no values.
All values live exclusively in leaf nodes.
Leaf nodes are doubly-linked — enabling O(k) sequential range scans after an O(log n) index seek.

B+ tree (order 3) after inserting age, city, email, name, zip:

              ┌──────────┐
              │  "name"  │   ← routing key only, no value
              └──────────┘
             /             \
 ┌────────────────────┐   ┌────────────────┐
 │ age=25  city=Lon   │◄─►│ name=Alice      │
 │ email=a@b.com      │   │ zip=EC1A        │
 └────────────────────┘   └────────────────┘
      leaf 0  ←prev=nil        leaf 1 →next=nil

Relation to this repo and FoundationDB:

The LevelDB SSTable in lab04/sstable.go is structurally a one-level B+ tree:

SSTable layout                  B+ tree equivalent
─────────────────────────────   ──────────────────────────────
data section (sorted records)   leaf pages (all values here)
index section (key → offset)    one internal routing node
16-byte footer                  file header with root page ID
varint variable-length          fixed 4096-byte pages
immutable after Finish()        copy-on-write (Redwood engine)

FoundationDB’s Redwood storage engine uses a full multi-level copy-on-write B+ tree over a page store, providing crash safety without an explicit WAL on the tree pages themselves.

Serialization: two page types

Internal page:
  [1B: type = 0x01]
  [2B: numKeys, LE]
  per key:   [2B keyLen][key bytes]        ← NO values in internal nodes
  per child: [8B child page ID, LE]        ← numKeys+1 entries

Leaf page:
  [1B: type = 0x02]
  [2B: numKeys, LE]
  [8B: prev leaf page ID]  (0xFF...FF = none)
  [8B: next leaf page ID]  (0xFF...FF = none)
  per record: [2B keyLen][2B valLen][key bytes][val bytes]

File header (page 0):
  [8B: magic = 0xB99EEF15B99EEF15]
  [8B: root page ID]
  [8B: total page count]

Go implementation

const (
    bpOrder    = 3
    bpPageSize = 4096
    bpMagic    = uint64(0xB99EEF15B99EEF15)
    bpInternal = byte(0x01)
    bpLeaf     = byte(0x02)
    bpNilPage  = ^uint64(0) // 0xFFFFFFFFFFFFFFFF
)

type bpNode struct {
    keys     [][]byte
    values   [][]byte  // leaf only
    children []*bpNode // internal only; len = len(keys)+1
    next     *bpNode   // leaf linked list →
    prev     *bpNode   // leaf linked list ←
    isLeaf   bool
}

type BPlusTree struct {
    root      *bpNode
    firstLeaf *bpNode
}

func NewBPlusTree() *BPlusTree {
    leaf := &bpNode{isLeaf: true}
    return &BPlusTree{root: leaf, firstLeaf: leaf}
}

func (t *BPlusTree) findLeaf(key []byte) *bpNode {
    n := t.root
    for !n.isLeaf {
        i := 0
        for i < len(n.keys) && bytes.Compare(key, n.keys[i]) >= 0 {
            i++
        }
        n = n.children[i]
    }
    return n
}

func (t *BPlusTree) Get(key []byte) ([]byte, bool) {
    leaf := t.findLeaf(key)
    for i, k := range leaf.keys {
        if bytes.Equal(k, key) {
            return leaf.values[i], true
        }
    }
    return nil, false
}

// RangeScan yields (key, value) for lo ≤ key ≤ hi using the leaf linked list.
func (t *BPlusTree) RangeScan(lo, hi []byte, fn func(key, value []byte)) {
    leaf := t.findLeaf(lo)
    for leaf != nil {
        for i, k := range leaf.keys {
            if bytes.Compare(k, lo) < 0 { continue }
            if bytes.Compare(k, hi) > 0 { return }
            fn(k, leaf.values[i])
        }
        leaf = leaf.next
    }
}

func (t *BPlusTree) Put(key, value []byte) {
    leaf := t.findLeaf(key)
    for i, k := range leaf.keys {
        if bytes.Equal(k, key) { leaf.values[i] = value; return }
    }
    i := sort.Search(len(leaf.keys), func(j int) bool {
        return bytes.Compare(leaf.keys[j], key) >= 0
    })
    leaf.keys   = append(leaf.keys,   nil)
    leaf.values = append(leaf.values, nil)
    copy(leaf.keys[i+1:],   leaf.keys[i:])
    copy(leaf.values[i+1:], leaf.values[i:])
    leaf.keys[i]   = key
    leaf.values[i] = value
    if len(leaf.keys) > 2*bpOrder-1 {
        t.splitLeaf(leaf)
    }
}

func (t *BPlusTree) splitLeaf(leaf *bpNode) {
    mid    := len(leaf.keys) / 2
    newLeaf := &bpNode{isLeaf: true}
    newLeaf.keys   = append(newLeaf.keys,   leaf.keys[mid:]...)
    newLeaf.values = append(newLeaf.values, leaf.values[mid:]...)
    leaf.keys   = leaf.keys[:mid]
    leaf.values = leaf.values[:mid]
    // Stitch linked list
    newLeaf.next = leaf.next
    newLeaf.prev = leaf
    if leaf.next != nil { leaf.next.prev = newLeaf }
    leaf.next = newLeaf
    t.insertIntoParent(leaf, newLeaf.keys[0], newLeaf)
}

func (t *BPlusTree) insertIntoParent(left *bpNode, key []byte, right *bpNode) {
    if left == t.root {
        newRoot := &bpNode{
            isLeaf:   false,
            keys:     [][]byte{key},
            children: []*bpNode{left, right},
        }
        t.root = newRoot
        return
    }
    parent := t.findParent(t.root, left)
    i := 0
    for i < len(parent.children) && parent.children[i] != left { i++ }
    parent.keys     = append(parent.keys,     nil)
    parent.children = append(parent.children, nil)
    copy(parent.keys[i+1:],      parent.keys[i:])
    copy(parent.children[i+2:],  parent.children[i+1:])
    parent.keys[i]       = key
    parent.children[i+1] = right
    if len(parent.keys) > 2*bpOrder-1 {
        t.splitInternal(parent)
    }
}

func (t *BPlusTree) splitInternal(n *bpNode) {
    mid  := len(n.keys) / 2
    push := n.keys[mid]
    sib  := &bpNode{isLeaf: false}
    sib.keys     = append(sib.keys,     n.keys[mid+1:]...)
    sib.children = append(sib.children, n.children[mid+1:]...)
    n.keys     = n.keys[:mid]
    n.children = n.children[:mid+1]
    if n == t.root {
        newRoot := &bpNode{
            isLeaf:   false,
            keys:     [][]byte{push},
            children: []*bpNode{n, sib},
        }
        t.root = newRoot
        return
    }
    t.insertIntoParent(n, push, sib)
}

func (t *BPlusTree) findParent(cur, target *bpNode) *bpNode {
    if cur.isLeaf { return nil }
    for _, child := range cur.children {
        if child == target { return cur }
        if p := t.findParent(child, target); p != nil { return p }
    }
    return nil
}

// SerializeLeafPage encodes a leaf node into bpPageSize bytes.
func SerializeLeafPage(n *bpNode, prevID, nextID uint64) []byte {
    page := make([]byte, bpPageSize)
    page[0] = bpLeaf
    binary.LittleEndian.PutUint16(page[1:3],  uint16(len(n.keys)))
    binary.LittleEndian.PutUint64(page[3:11], prevID)
    binary.LittleEndian.PutUint64(page[11:19], nextID)
    off := 19
    for i, k := range n.keys {
        binary.LittleEndian.PutUint16(page[off:], uint16(len(k))); off += 2
        copy(page[off:], k); off += len(k)
        v := n.values[i]
        binary.LittleEndian.PutUint16(page[off:], uint16(len(v))); off += 2
        copy(page[off:], v); off += len(v)
    }
    return page
}

// SerializeInternalPage encodes a routing node (keys only, no values).
func SerializeInternalPage(n *bpNode, childPageIDs []uint64) []byte {
    page := make([]byte, bpPageSize)
    page[0] = bpInternal
    binary.LittleEndian.PutUint16(page[1:3], uint16(len(n.keys)))
    off := 3
    for _, k := range n.keys {
        binary.LittleEndian.PutUint16(page[off:], uint16(len(k))); off += 2
        copy(page[off:], k); off += len(k)
    }
    for _, id := range childPageIDs {
        binary.LittleEndian.PutUint64(page[off:], id); off += 8
    }
    return page
}

Python implementation

BP_ORDER    = 3
BP_PAGE     = 4096
BP_MAGIC    = 0xB99EEF15B99EEF15
BP_INTERNAL = 0x01
BP_LEAF     = 0x02
BP_NIL      = 0xFFFFFFFFFFFFFFFF

class _BPNode:
    __slots__ = ('keys', 'values', 'children', 'next', 'prev', 'is_leaf')
    def __init__(self, is_leaf=True):
        self.keys:     list[bytes]    = []
        self.values:   list[bytes]    = []   # leaf only
        self.children: list['_BPNode'] = []  # internal only
        self.next: Optional['_BPNode'] = None
        self.prev: Optional['_BPNode'] = None
        self.is_leaf = is_leaf

class BPlusTree:
    """B+ tree: values in leaves only; leaf linked-list for range scans."""

    def __init__(self):
        leaf = _BPNode(is_leaf=True)
        self._root       = leaf
        self._first_leaf = leaf

    def _find_leaf(self, key: bytes) -> _BPNode:
        n = self._root
        while not n.is_leaf:
            i = 0
            while i < len(n.keys) and key >= n.keys[i]: i += 1
            n = n.children[i]
        return n

    def get(self, key: bytes) -> Optional[bytes]:
        leaf = self._find_leaf(key)
        for i, k in enumerate(leaf.keys):
            if k == key: return leaf.values[i]
        return None

    def put(self, key: bytes, value: bytes):
        leaf = self._find_leaf(key)
        for i, k in enumerate(leaf.keys):
            if k == key: leaf.values[i] = value; return
        i = 0
        while i < len(leaf.keys) and key > leaf.keys[i]: i += 1
        leaf.keys.insert(i, key); leaf.values.insert(i, value)
        if len(leaf.keys) > 2 * BP_ORDER - 1:
            self._split_leaf(leaf)

    def _split_leaf(self, leaf: _BPNode):
        mid      = len(leaf.keys) // 2
        new_leaf = _BPNode(is_leaf=True)
        new_leaf.keys   = leaf.keys[mid:]
        new_leaf.values = leaf.values[mid:]
        leaf.keys   = leaf.keys[:mid]
        leaf.values = leaf.values[:mid]
        new_leaf.next = leaf.next
        new_leaf.prev = leaf
        if leaf.next: leaf.next.prev = new_leaf
        leaf.next = new_leaf
        self._insert_into_parent(leaf, new_leaf.keys[0], new_leaf)

    def _insert_into_parent(self, left: _BPNode, key: bytes, right: _BPNode):
        if left is self._root:
            r = _BPNode(is_leaf=False)
            r.keys = [key]; r.children = [left, right]
            self._root = r; return
        parent = self._find_parent(self._root, left)
        i = parent.children.index(left)
        parent.keys.insert(i, key)
        parent.children.insert(i + 1, right)
        if len(parent.keys) > 2 * BP_ORDER - 1:
            self._split_internal(parent)

    def _split_internal(self, n: _BPNode):
        mid  = len(n.keys) // 2
        push = n.keys[mid]
        sib  = _BPNode(is_leaf=False)
        sib.keys     = n.keys[mid+1:]
        sib.children = n.children[mid+1:]
        n.keys     = n.keys[:mid]
        n.children = n.children[:mid+1]
        if n is self._root:
            r = _BPNode(is_leaf=False)
            r.keys = [push]; r.children = [n, sib]
            self._root = r; return
        self._insert_into_parent(n, push, sib)

    def _find_parent(self, cur: _BPNode, target: _BPNode) -> Optional[_BPNode]:
        if cur.is_leaf: return None
        for child in cur.children:
            if child is target: return cur
            p = self._find_parent(child, target)
            if p: return p
        return None

    def range_scan(self, lo: bytes, hi: bytes):
        """O(log n + k) range scan using leaf linked list."""
        leaf = self._find_leaf(lo)
        while leaf is not None:
            for i, k in enumerate(leaf.keys):
                if k < lo: continue
                if k > hi: return
                yield k, leaf.values[i]
            leaf = leaf.next

    def __iter__(self):
        """Full scan via leaf linked list — O(n), no tree traversal needed."""
        leaf = self._first_leaf
        while leaf is not None:
            yield from zip(leaf.keys, leaf.values)
            leaf = leaf.next

    def serialize_leaf(self, n: _BPNode,
                       prev_id: int = BP_NIL,
                       next_id: int = BP_NIL) -> bytes:
        buf = bytearray(BP_PAGE)
        buf[0] = BP_LEAF
        struct.pack_into('<H', buf, 1, len(n.keys))
        struct.pack_into('<Q', buf, 3,  prev_id)
        struct.pack_into('<Q', buf, 11, next_id)
        off = 19
        for k, v in zip(n.keys, n.values):
            struct.pack_into('<HH', buf, off, len(k), len(v)); off += 4
            buf[off:off+len(k)] = k; off += len(k)
            buf[off:off+len(v)] = v; off += len(v)
        return bytes(buf)

    def serialize_internal(self, n: _BPNode,
                           child_ids: list[int]) -> bytes:
        """Internal page stores keys only — no values."""
        buf = bytearray(BP_PAGE)
        buf[0] = BP_INTERNAL
        struct.pack_into('<H', buf, 1, len(n.keys))
        off = 3
        for k in n.keys:
            struct.pack_into('<H', buf, off, len(k)); off += 2
            buf[off:off+len(k)] = k; off += len(k)
        for cid in child_ids:
            struct.pack_into('<Q', buf, off, cid); off += 8
        return bytes(buf)

Example: insert age/city/name + extras, range scan, serialize pages

bpt = BPlusTree()
bpt.put(b"age",   b"25")
bpt.put(b"city",  b"London")
bpt.put(b"email", b"alice@example.com")
bpt.put(b"name",  b"Alice")
bpt.put(b"zip",   b"EC1A")

print("All keys (leaf linked-list, O(n) scan):")
for k, v in bpt:
    print(f"  {k.decode():8s} -> {v.decode()}")

print("\nRange scan [city .. name]:")
for k, v in bpt.range_scan(b"city", b"name"):
    print(f"  {k.decode():8s} -> {v.decode()}")

# Serialize leaf 0
leaf0     = bpt._first_leaf
leaf1_id  = 1 if leaf0.next else BP_NIL
page0     = bpt.serialize_leaf(leaf0, prev_id=BP_NIL, next_id=leaf1_id)
print(f"\nLeaf page 0: {len(page0)} bytes")
print(f"  type    = {page0[0]:#x}  (0x02 = leaf)")
print(f"  numKeys = {struct.unpack_from('<H', page0, 1)[0]}")
print(f"  prevID  = {struct.unpack_from('<Q', page0, 3)[0]:#x}")
print(f"  nextID  = {struct.unpack_from('<Q', page0, 11)[0]:#x}")

Output:

All keys (leaf linked-list, O(n) scan):
  age      -> 25
  city     -> London
  email    -> alice@example.com
  name     -> Alice
  zip      -> EC1A

Range scan [city .. name]:
  city     -> London
  email    -> alice@example.com
  name     -> Alice

Leaf page 0: 4096 bytes
  type    = 0x2  (0x02 = leaf)
  numKeys = 2
  prevID  = 0xffffffffffffffff
  nextID  = 0x1

B+ Tree ↔ LevelDB SSTable equivalence

SSTable (lab04/sstable.go)              B+ Tree
───────────────────────────────────     ───────────────────────────────────
varint-encoded data records             leaf page records (fixed-size pages)
sorted by CompareInternal               sorted by Compare/CompareInternal
index: (key → file offset) array        internal page: (key → child page ID)
16-byte footer: indexOffset + magic     file header: root page ID + magic
immutable after Finish() + fdatasync    copy-on-write pages (Redwood engine)
flushed whole from MemTable             built incrementally, split on overflow

FoundationDB’s Redwood engine extends the SSTable idea to a full multi-level B+ tree with copy-on-write pages, giving crash safety without a WAL on the tree pages themselves — only the set of committed page replacements is journaled.

In real database engines

InnoDB (storage/innobase/btr/, storage/innobase/page/) InnoDB is the reference B+ tree database engine. Every table has a clustered index — the primary key B+ tree whose leaves contain the full row — plus zero or more secondary indexes whose leaves contain (secondary_key, primary_key). Key details:

Page size: 16 KiB (configurable to 4/8/32/64 KiB in MySQL 8.0)
Page type: FIL_PAGE_INDEX (0x45BF)
Page header includes: PAGE_LEVEL (0 = leaf), PAGE_N_RECS, PAGE_PREV and PAGE_NEXT (the leaf linked list — same as our prev/next pointers)
Records within a page are stored as a singly-linked list with a page directory (sparse array of slot offsets) for O(log n) binary search within the page
Split policy: fill factor ~15/16 for sequential inserts; ~1/2 for random inserts (to leave room for future inserts and reduce immediate re-splits)
btr_cur_search_to_nth_level() — the core tree descent function in btr0cur.cc, analogous to our _find_leaf()

PostgreSQL nbtree (src/backend/access/nbtree/) Postgres implements B+ trees in the nbtree access method:

Page size: 8 KiB (same as heap pages)
BTPageOpaqueData appended to every page: btpo_prev, btpo_next (leaf sibling links), btpo_level, btpo_flags
High keys: the rightmost key of each non-rightmost page is stored as a special “high key” item — used to detect concurrent page splits without locks
Concurrent modifications: nbtinsert.c uses a stacked-latch protocol (hold parent latch while descending) rather than a global tree lock
Index-only scans: if all queried columns are in the index, Postgres can return data directly from the B+ tree leaf without touching the heap

MongoDB WiredTiger (src/third_party/wiredtiger/src/btree/) WiredTiger provides both a row-store B+ tree and a column-store B+ tree:

WT_PAGE struct in wt_internal.h: pg_intl_* fields for internal pages, pg_row_* for leaf row-store pages
Reconciliation: dirty in-memory pages are written to disk during checkpoints (analogous to LevelDB compaction writing new SSTables)
Eviction: a background eviction thread maintains a memory budget by writing dirty pages and discarding clean ones
MVCC via update chains: instead of a sequence number in the key, WiredTiger chains WT_UPDATE structs off each leaf record — the read timestamp determines which update is visible

FoundationDB Redwood (fdbserver/KeyValueStoreRedwood.actor.cpp) Redwood is a copy-on-write B+ tree purpose-built for FoundationDB:

BTreePage struct with variable-length delta-encoded records (each key stores only the bytes that differ from the previous key — same idea as LevelDB’s prefix compression in data blocks)
Every write produces new page versions at affected leaf → up to root; the old pages remain accessible to concurrent readers at older versions (MVCC without a separate undo log)
A pager (DWALPager) under Redwood provides atomic page replacement: it journals the set of {old page ID → new page ID} mappings before committing them, providing the durability guarantee without a full WAL

Filesystem B+ trees

Filesystem	Structure	Details
ext4	`htree` (dir_index)	2-level hash tree over directory entries; `dx_root` + `dx_node` structs in `fs/ext4/namei.c`
APFS	Object Map + B-tree	Each volume has a B-tree mapping object ID → physical block; `apfs_btree_node_phys` struct
NTFS	`$INDEX_ALLOCATION`	B+ tree of directory entries; `INDEX_BLOCK` pages with sibling links
HFS+	Catalog File	B*-tree (nodes redistributed before split, higher fill factor than B+)

Key design lesson: B+ trees dominate on-disk indexes because the leaf linked list turns a B-tree (good for point lookups) into a structure that is also optimal for range scans — the most common database workload. Every component of the page format we designed above (type byte, numKeys, prev/next page IDs, per-record keyLen+valLen) appears verbatim in InnoDB, Postgres, and WiredTiger. The only variation is page size and whether delta/prefix encoding is applied to records within a page.

Summary: all data structures compared

Structure	Height	Insert	Point Lookup	Range Scan	Serialization on disk	Used in this repo
Skip List	O(log n) expected	O(log n) expected	O(log n) expected	O(k) forward	Flat sorted dump	LevelDB MemTable (`lab02`)
Red-Black Tree	≤ 2 log₂(n+1)	O(log n) worst-case	O(log n) worst-case	O(k) in-order	Flat sorted dump	Equivalent MemTable substitute
B-Tree	log_m(n)	O(log n)	O(log n)	O(k·m)	Fixed-size pages	SQLite backend (`option-a-sqlite`, `option-b-sqlite`)
B+ Tree	log_m(n)	O(log n)	O(log n)	O(log n + k)	Fixed pages + leaf links	SSTable (`lab04`), FDB Redwood
Min-Heap	log n	O(log n) push	O(1) peek	N/A (ephemeral)	Not persisted	Compaction K-way merge (`lab06`)
WAL	1 (append-only)	O(1) amortized	N/A	Sequential replay	Framed records (len+CRC)	Crash recovery (`lab01`)

All six structures from labs 01–08 and the three comparison structures are tied together in the capstone engine at lab08/db.go.

Summary: data structures touched by `db.Put("name","Alice")`

Step	Data structure	Operation	Lab	Go source
1	Internal Key	Encode `"name" \|\| (seqNum<<8\|TYPE_VALUE)`	02	`lab02/key.go`
2	WAL	Append framed record + fdatasync	01	`lab01/wal.go`
3	Skip List	`Put(internalKey, "Alice")` in O(log n)	02	`lab02/skiplist.go`
4	MemTable	Thin wrapper; track size for flush trigger	02	`lab02/memtable.go`
5 (flush)	SSTable Builder	`Add` per sorted key; varint encoding	04	`lab04/sstable.go`
6 (compact)	Min-Heap	K-way merge of all L0+L1 iterators	06	`lab06/iter.go`
—	Red-Black Tree	Alternative in-memory MemTable index	—	—
—	B-Tree	SQLite page storage (`option-*-sqlite` labs)	—	`option-a-sqlite/`
—	B+ Tree	SSTable ≅ 1-level B+ tree; FDB Redwood	—	`lab04/sstable.go`

All structures wired together in the capstone engine at lab08/db.go.

Keyboard shortcuts

FoundationDB Layers — Go Implementations