Algorithms · Cluster
Searching and Indexing
Trees, hashing, and structures that answer lookup queries.
- 01 Lower Bound, Upper Bound, and the Invariant That Makes Binary Search Correct Why binary search is best expressed as a loop invariant over a half-open interval, how lower and upper bound answer different questions, and which arithmetic breaks first.
- 02 Interpolation Search and What Uniform Key Distribution Buys How probing by estimated position turns logarithmic search into log-log search, the exact arithmetic it needs, and the degenerate inputs that make it linear.
- 03 Eytzinger Layout: Storing a Search Tree in Level Order How laying out a binary search tree in breadth-first order removes pointer chasing, enables branch-free traversal and prefetching, and what it costs on updates.
- 04 B-Tree Fanout Arithmetic and the Cost of a Point Lookup Why page-sized nodes give B-trees a fanout in the hundreds, how that collapses tree height to three or four levels, and where the arithmetic stops paying off.
- 05 Extendible Hashing and Why the Directory Doubles How a trie of hash bits lets a file grow one bucket at a time, why the directory doubles rather than the file, and what the indirection costs on every probe.
- 06 Probe Sequences in Open-Addressed Hash Tables How linear, quadratic and double hashing differ in clustering behaviour, why deletion needs tombstones or backward shifting, and what Robin Hood ordering buys.
- 07 Minimal Perfect Hashing for Static Key Sets How two-level displacement schemes map a fixed set of keys onto consecutive slots with no collisions, and why the result costs about two bits per key.
- 08 Posting List Encoding and the Cost of a Term Lookup How inverted indexes compress sorted document lists with delta and variable-byte codes, why skipping is needed for intersections, and where compression stops paying.
- 09 Learned Indexes: Fitting a Function Instead of Storing Keys How a model that predicts a key position can replace a B-tree search, what the error bound guarantees, and why the last mile is always a search.
- 10 Bitmap and Roaring Indexes for Combining Predicates How one bit per document per value makes conjunctions word-parallel, why the space cost forces chunked container formats, and where the crossover thresholds sit.