← Back
Home › Systems › Databases and storage engines

position-db

game position database with prefix and bitmap indexes

Lichess opening explorer

SystemTechniques · 2Primitives · 23 position-db External merge sortsearch-sort · medium: Sort data larger than RAM: write memory-sized sorted runs, then k-way merge them with large sequential buffers; terabytes in one merge pass.›LSM-treestorage · medium: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.›Delta encodingcompression · low: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›Prefix compressioncompression · low: Front coding / shared-prefix truncation of sorted keys in blocks and index pagesRoaring bitmapscompression · low: Compressed set of 32-bit integers in 64K-value chunks, each a sorted array, bitmap or run list; fast intersections, the standard for bitmap indexes.›Varint (LEB128)compression · low: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.›Zstandard (zstd)compression · low: LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.›Bloom filterdata-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.›Compact state encodingdata-structures · low: Pack a game position into a few fixed bytes (24 for chess: occupancy bitboard plus nibbles) for training data and dedupeMinimal perfect hashingdata-structures · low: A hash function mapping n fixed keys to 0..n-1 without collisions, in 1.5-4 bits per key; the keys themselves are not stored.›Bitboardsgame-ai · low: One 64-bit word per set of up to 64 items, so set algebra becomes shifts, ANDs and table lookups; magic bitboards give ray queries in one multiply.›Zobrist hashinggame-ai · low: A state's hash is the XOR of one random 64-bit key per (item, slot) fact that holds in it, updated in a few XORs per change.›mmap and the page cachehardware-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.›Bulk loadingstorage · low: Build an index bottom-up from sorted input (SST ingest, B-tree bulk load) instead of point insertsLsm merge operatorstorage · low: Store read-modify-write operands (counters, appends) and fold them at read/compaction timeBuffer pools for zero-allocation I/Ohardware-os · low: Preallocate a fixed set of aligned I/O buffers and recycle them through a free list, so the hot path never mallocs, faults or unmaps. The bounded count doubles as back pressure.›K way mergesearch-sort · low: Merge k sorted streams with a heap or loser tree (merging iterators)Pattern-defeating quicksort (pdqsor…search-sort · low: Introsort successor: quicksort with adaptive pivots, linear on sorted and equal-heavy input, heapsort fallback; the unstable sort of Go and (until 1.81) Rust.›+ 7 more primitives

Similar systems

Share the most building blocks with this one.

lsm-engine 22 %timeseries-db 17 %