Search and Data Structures §
Search and data structures study how to organize data so that algorithms can access it cheaply. They are relevant whenever a program must store, retrieve, or update large collections of items: from a single in-memory hash table to a distributed database serving millions of queries per second.
Utility §
- They choose the representation that makes the dominant access pattern cheap.
- They bound the cost of lookup, insertion, and deletion in terms of collection size.
- They compose: a database index is a B-tree, a search engine is an inverted index of posting lists, a graph is a set of adjacency lists.
Details
The five classes partition search problems by the access pattern that defines the query. Each builds on the previous: flat structures give positional access with no ordering; hierarchical structures add ordering for key access; text structures exploit the alphabet to match patterns; relational structures combine multiple key dimensions with predicates; graph structures generalize to arbitrary connectivity.
History §
- 1948: Knuth formalizes the asymptotic analysis of sorting and searching algorithms.
- 1972: B-trees and B+ trees become the standard index structure for relational databases.
- 1996: O’Neil et al. introduce LSM-trees for write-optimized storage.
- 2003: Bloom filters gain widespread use in distributed systems for probabilistic membership testing.
Classes §
| Subtopic | Access pattern | Search | Insert / Delete | Space |
|---|---|---|---|---|
| Lists | Positional (index into a sequence) | O(1) by index, O(n) by value | O(1) amortized (vector) | O(n) |
| Key-Value Stores | Key-based (hash or ordered) | O(1) expected / O(log n) | O(1) / O(log n) | O(n) |
| Text Search | Pattern / substring | O(n+m) to O(n log n) | O(n) | O(n) to O(n log n) |
| Database Theory | Relational (predicate over tuples) | O(log n) (indexed) | O(log n) | O(n) + index overhead |
| Graphs | Connectivity (adjacency) | O(n+m) traversal | O(1) per edge | O(n+m) |
Authoritative sources