← Back
Home › Systems › Databases and storage engines

graph-db

graph database

Neo4j

SystemTechniques · 8Primitives · 25 graph-db Pagerankgraphs · medium: Power-iteration PageRank on a sparse graph with damping and dangling nodesBuffer poolstorage · 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.›Cardinality estimationstorage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizerMVCCstorage · medium: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.›Query optimizerstorage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selectionWorst case optimal joinstorage · medium: Leapfrog triejoin/generic join for cyclic graph patternsJoin order dynamic programmingstorage · medium: DPccp and DPhyp enumeration of join orders with cost models; greedy fallback for many joinsSparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›Hash joinstorage · low: 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.›Recursive-descent parsingcompilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Dijkstra's algorithmgraphs · low: Single-source shortest paths with non-negative edge weights by settling vertices in order of distance with a priority queue.›Union-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›B+ treestorage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.›Index-free adjacencystorage · low: 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.›Write-ahead logstorage · 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.›Reproducible reductionnumerics · low: Order-independent floating-point sums (fixed order, Kahan, binned) for bit-for-bit reproducibilityfsync, O_DSYNC and O_DIRECThardware-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 CLOCKsystems · 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.›S3-FIFOsystems · 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.›HyperLogLogdata-structures · low: Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.›Quantile sketchesdata-structures · low: Mergeable quantile sketches: t-digest, DDSketch, HDR histogramsReservoir samplingdata-structures · low: Uniform k-sample from a stream of unknown length (Algorithm R/L)+ 1 more techniques+ 9 more primitives

Similar systems

Share the most building blocks with this one.

relational-db 28 %embedded-sql 26 %knowledge-graph 24 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

TAOMeta Platforms