Concise reference outline for building high-performance, super lightweight databases (key-value, document, relational, graph, spatial, vector, full-text/search). From hardware/memory basics to scalability. Use as blueprint for implementing any DB type.
Materials:
Book: Designing Data-Intensive Applications | Goodreads | Oreilly
Book: Database Internals: A deep-dive into how distributed data systems work | Web | Goodreads
Youtube: CMU Database Group
The Principles
Hardcore Definition of Database
Append fact -> Force it to stay -> Never lie about it
Storing the Facts: The Fundamental Operation
Place to store the facts:
Memory: very fast access (pure in-memory database)
Disk: slower but survive crashes
Hybrid: Juggling around between to get both benefit. This is how most database operate
Writing to Disk
Program -> OS -> Disk
The steps of persistence:
Programs (Microsoft Word, Inkscape, Blender, PostgreSQL, first-timer learning to write a file in PHP, YugabyteDB, SurrealDB, ArangoDB, Redis persistence option) instruct the OS (write()) and provide data to be written to disk.
Without specific additional instructions, the OS does not write the data immediately to disk; instead, it performs some internal useful management first. Here, the programs delegate the responsibility of persisting data to the OS. The question is, what if the OS crashes before it persists the data to disk? Then the data is lost. Some databases are okay with this, but stricter databases won't let this happen.
The program can give instructions so the OS immediately flushes the data to disk through fsync() (Linux, Mac) FlushFileBuffers (Windows).
Different writing optimization strategies control when and how the write() and fsync() occur between the program and the OS.
The Knowledges
1. Hardware & Memory Fundamentals
CPU/Memory Hierarchy: Registers > L1/L2/L3 cache > RAM; volatility, LRU eviction for caching; NUMA awareness for multi-socket.
Storage Basics: HDD (seek time, rotational latency), SSD (NAND flash, wear-leveling, TRIM); 4KB-8KB pages/blocks; NVMe for low latency.
I/O Patterns: Sequential (fast) vs. random (slow); read/write amplification in flash; prefetching, batching.
2. Filesystem & OS Abstractions
Files & Blocks: Inodes, extents; page cache, direct I/O, fsync/fdatasync/O_DIRECT for durability/low-latency.
Concurrency Primitives: Mutexes, spinlocks, atomics, memory barriers, RCU for read-heavy.
Scheduling: Thread pools, async I/O (epoll/io_uring/AIO); work-stealing queues.
3. Core Data Structures
Hash Tables: Open addressing/chaining, resizing, load factors (0.7), SIMD for lookups.
Trees: Binary search, B/B+-trees (balanced, disk-optimized), LSM-trees (write-optimized), tries/prefix trees, HNSW/IVF for vectors.
Others: Dynamic arrays (amortized append), skip lists, bloom filters, adjacency lists (CSR for graphs), quantizers for vectors.
Serialization: Encode/decode keys/values (varint/zigzag, delta/prefix compression); block compression (Snappy/Zstd/LZ4) for lightweight storage.
4. Storage Engines
Page-Oriented: Heap files, B+ indexes (InnoDB/PostgreSQL); lightweight WAL.
Log-Structured (LSM): Memtable (skiplist/hash), immutable SSTables, leveled/tiered compaction (RocksDB/fjall); size-tiered for lightweight.
In-Memory: Hash/skiplist + snapshots, AOF/RDB persistence (Redis); memory-mapped files.
Hybrid/Columnar: Row vs. column stores (Parquet); append-only logs for vectors.
5. Indexing Strategies
Basics: Primary/unique, secondary/clustered; covering indexes, multi-column composites; point/range scans.
Spatial: R-trees, Quad-trees, Geohash/Hilbert curves, STR-trees.
Vector: HNSW, IVF-PQ, DiskANN; ANN metrics (cosine/L2/IP); filtering + reranking.
Full-Text: Inverted indexes, postings lists, skip lists; stemming, TF-IDF, BM25.
Hybrid Techniques: Combine inverted + vector + scalar filters; late fusion, Reciprocal Rank Fusion (RRF), multi-modal retrieval.
6. Database Types & Key Traits
Key-Value: Simple hash + sorted runs (LevelDB/RocksDB/fjall); GET/PUT ops, lightweight LSM.
Document: Nested JSON/BSON, dynamic schema, secondary indexes (MongoDB); compact storage.
Relational: Tables/rows, ACID SQL, joins/normalization (PostgreSQL/pgvector); MVCC lightweight.
Graph: Nodes/properties/edges/rels, traversals (BFS/DFS/A*), indexes (Neo4j/ArangoDB); CSR adjacency.
Spatial: Geometry types (points/lines/polygons), spatial indexes/functions (PostGIS).
Vector: Embeddings/vectors, ANN indexes (HNSW/FAISS), similarity search (cosine/euclidean); hybrid filters (Milvus/Pinecone lite).
Full-Text/Search: Lucene-based inverted indexes, analyzers, relevance (Elasticsearch); lightweight tokenization.