Databases & storage

Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.

Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.

Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.

Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.

Store each node's edges as direct references to neighbouring records, so a hop costs O(degree) pointer reads instead of an index search; know when plain tables or CSR beat it.

Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.

Three-pass crash recovery (analysis, redo, undo) for steal/no-force buffer pools; repeats history, then rolls back losers with compensation log records.

Let concurrent committers share one log write and fsync; throughput grows with concurrency while each commit still waits at most about two fsyncs.

Periodic base backups plus a continuously archived change log let you rebuild the state as of any instant, then branch from there.

Make the log the store: append every write, point an index at the newest copy, reclaim space by copying live records forward.

Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.

Transactions take shared/exclusive locks and release none until they stop acquiring; strict 2PL holds them to commit and guarantees serializability.

Run transactions without locks, record what they read, and validate at commit that nothing changed; fastest when conflicts are rare.

Find transactions waiting on each other in a cycle (wait-for graph), abort one, or order lock requests so no cycle can form.

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.

Store each column contiguously so analytic scans read only the columns they need, compress well and run as tight SIMD loops.

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.

Cut an N-dimensional array into a regular grid of independently compressed blocks, so a slice read touches only the overlapping blocks and writers to different blocks run in parallel.

Cut a table into fixed-interval time blocks so queries read only overlapping blocks and retention drops a whole block as one metadata change.

Store each series as immutable compressed chunks of consecutive samples behind a small time index; a range query decodes only the chunks that overlap it.

Store each blob under the hash of its bytes: immutable, deduplicated by construction, self-verifying on every read, and composable into Merkle trees.

Query operators pass batches of about 1-2K values per column instead of single tuples, amortizing interpretation overhead and enabling tight SIMD loops.

Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.

Sort both inputs on the key, then advance two cursors in lockstep and emit matching runs; cheap on sorted inputs and good for range joins.

Process old data in bounded key ranges, one short transaction per chunk, with a saved checkpoint and idempotent writes, so a crash resumes and live traffic never waits.

Decode the database's own commit log into row-change events in commit order, with a resume position, so any consumer can mirror the data exactly.

Fold raw events into one mergeable partial aggregate per time bucket and dimension key, then merge fine buckets into coarser ones, so long ranges read few rows and stay exact.

Decide which records describe the same real-world thing: block to cut the pair space, score pairs with a probabilistic model, cluster the matches transitively.

Tokenize XML into start, text and end events in constant memory, so a few fields can be extracted from huge, broken or hostile documents.