mhtirogla
Home
Systems
API
Pricing
About
Log in
← Back
Home
›
Systems
›
Databases and storage engines
btree-engine
embedded B+tree storage engine
LMDB, WiredTiger
System
Techniques · 4
Primitives · 19
btree-engine
B link tree
storage · medium: Lehman-Yao B-tree with right-links and high keys for latch-free reads and concurrent splits
Buffer pool
storage · medium: The database's own page cache (frames, page table, pin counts, dirty bits, replacement) so it, not the OS, controls eviction, write order and I/O.
›
Copy on write b tree
storage · medium: Append-only/shadow-paging B+tree: copy the root-to-leaf path on write, atomic root swap (LMDB style)
MVCC
storage · medium: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.
›
B+ tree
storage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.
›
fsync, O_DSYNC and O_DIRECT
hardware-os · low: What fsync, fdatasync, O_DSYNC, O_DIRECT and F_FULLFSYNC really guarantee on Linux and macOS, and the exact call sequences for crash-safe files.
›
LRU and CLOCK
systems · low: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.
›
Free space management
storage · low: Free-space bitmaps, extent B-trees and space maps; allocation policies and fragmentation
Prefix compression
compression · low: Front coding / shared-prefix truncation of sorted keys in blocks and index pages
Hazard pointers
concurrency · low: Readers publish the exact pointers they are about to dereference; a reclaimer frees retired objects that no published hazard names, giving bounded garbage.
›
Advisory file locking
hardware-os · low: Fcntl/flock byte-range and whole-file locks for multi-process access to one file
CRC32C checksums
hardware-os · low: The Castagnoli CRC-32 with dedicated instructions on x86 (SSE4.2) and ARMv8. It is the standard fast integrity check for storage blocks, logs and network frames.
›
mmap and the page cache
hardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.
›
Group commit
storage · low: Let concurrent committers share one log write and fsync; throughput grows with concurrency while each commit still waits at most about two fsyncs.
›
Slotted pages
storage · low: Fixed-size page layout for variable-length records, with a slot array growing from the front and data from the back; stable record IDs despite compaction.
›
Write-ahead log
storage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.
›
Epoch-based reclamation
concurrency · low: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.
›
Seqlock
concurrency · low: Readers copy shared data optimistically and retry if a sequence counter changed; zero reader writes, so reads scale perfectly with a single fast writer.
›
S3-FIFO
systems · low: Three FIFO queues (small, main, ghost) that evict one-hit wonders quickly and keep reused objects; low miss ratios with no list moves on hits.
›
Futex-based mutex
concurrency · low: A mutex that is one atomic word in user space and enters the kernel (futex wait/wake) only under contention; how std and glibc locks work.
›
+ 3 more primitives
System
Techniques · 4
Primitives · 19
btree-engine
B link tree
storage · medium: Lehman-Yao B-tree with right-links and high keys for latch-free reads and concurrent splits
Buffer pool
storage · medium: The database's own page cache (frames, page table, pin counts, dirty bits, replacement) so it, not the OS, controls eviction, write order and I/O.
›
Copy on write b tree
storage · medium: Append-only/shadow-paging B+tree: copy the root-to-leaf path on write, atomic root swap (LMDB style)
MVCC
storage · medium: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.
›
B+ tree
storage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.
›
fsync, O_DSYNC and O_DIRECT
hardware-os · low: What fsync, fdatasync, O_DSYNC, O_DIRECT and F_FULLFSYNC really guarantee on Linux and macOS, and the exact call sequences for crash-safe files.
›
LRU and CLOCK
systems · low: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.
›
Free space management
storage · low: Free-space bitmaps, extent B-trees and space maps; allocation policies and fragmentation
Prefix compression
compression · low: Front coding / shared-prefix truncation of sorted keys in blocks and index pages
Hazard pointers
concurrency · low: Readers publish the exact pointers they are about to dereference; a reclaimer frees retired objects that no published hazard names, giving bounded garbage.
›
Advisory file locking
hardware-os · low: Fcntl/flock byte-range and whole-file locks for multi-process access to one file
CRC32C checksums
hardware-os · low: The Castagnoli CRC-32 with dedicated instructions on x86 (SSE4.2) and ARMv8. It is the standard fast integrity check for storage blocks, logs and network frames.
›
mmap and the page cache
hardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.
›
Group commit
storage · low: Let concurrent committers share one log write and fsync; throughput grows with concurrency while each commit still waits at most about two fsyncs.
›
Slotted pages
storage · low: Fixed-size page layout for variable-length records, with a slot array growing from the front and data from the back; stable record IDs despite compaction.
›
Write-ahead log
storage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.
›
Epoch-based reclamation
concurrency · low: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.
›
Seqlock
concurrency · low: Readers copy shared data optimistically and retry if a sequence counter changed; zero reader writes, so reads scale perfectly with a single fast writer.
›
S3-FIFO
systems · low: Three FIFO queues (small, main, ghost) that evict one-hit wonders quickly and keep reused objects; low miss ratios with no list moves on hits.
›
Futex-based mutex
concurrency · low: A mutex that is one atomic word in user space and enters the kernel (futex wait/wake) only under contention; how std and glibc locks work.
›
Memory ordering
concurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.
›
SIMD programming
hardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.
›
Virtual memory and the TLB
hardware-os · low: How page tables and TLBs translate every address, what TLB reach means, and when 2 MiB or 1 GiB huge pages pay off on Linux.
›
Copy for AI
Similar systems
Share the most building blocks with this one.
relational-db
31 %
embedded-sql
30 %
filesystem
27 %
lsm-engine
26 %
wide-column
25 %