8 Data Structures Used in Databases

__omp_shell("")

Database performance does not come from magic SQL optimisers. It comes from concrete data structures chosen to make certain operations cheap and other operations acceptable. When you understand those structures, you can predict why one engine excels at point reads, another absorbs writes gracefully, and a third shines at text search or analytics.

1. B-tree

B-trees are a default index structure in many relational databases because they handle a balanced mix of inserts, point lookups, and range scans. Their branching factor is tuned for storage pages, so each lookup touches relatively few disk blocks. They are a strong general-purpose choice when ordered traversal matters.

2. LSM tree

Log-structured merge trees favour write throughput. Instead of updating many random disk locations immediately, they buffer writes in memory and flush sorted immutable files later. This makes ingestion fast, especially on spinning disks and SSDs, but it shifts cost into compaction and read amplification. Fast writes are paid for somewhere.

3. Hash index

Hash indexes are built for exact-match lookups. If you already know the key and do not care about ordering, hashing can be very efficient. The weakness is that range queries, prefix scans, and ordered pagination are poor fits. A structure that is brilliant for id = 42 tells you little about id > 42.

4. Skip list

A skip list maintains ordered data through multiple probabilistic layers of forward pointers. It offers search and update performance similar in spirit to balanced trees, but with a simpler implementation model. Some in-memory databases and memtables use skip lists because they provide ordered traversal without the bookkeeping of complex rebalancing logic.

5. Bloom filter

A Bloom filter is a compact probabilistic structure that answers either maybe or definitely not. Storage engines use it to avoid unnecessary reads from disk when a key is certainly absent from an SSTable or segment. False positives are possible, false negatives are not. That tradeoff is useful when disk I/O is expensive and memory is cheaper.

6. SSTable

A sorted string table is an immutable, sorted file format used heavily in LSM-based systems. Because entries are stored in order, the engine can use sparse indexes, block scans, and efficient sequential reads. Immutability simplifies recovery and concurrency, but it also means background compaction is needed to merge old and new files over time.

7. Inverted index

Full-text search systems need to answer a different question from relational indexes: which documents contain this term? An inverted index maps terms to posting lists of matching documents or rows. This makes keyword search, phrase search, and ranking feasible at scale, but it also requires tokenisation, normalisation, and ongoing maintenance when documents change.

8. Columnar segment

Analytical databases often store values column by column rather than row by row. That layout makes scans, vectorised execution, and compression much more efficient when queries touch only a subset of columns across many rows. The tradeoff is that small transactional updates are often less natural than they are in row-oriented systems.

Why engines combine them

Real databases rarely rely on one structure alone. An LSM engine may combine a write-ahead log, a skip list memtable, Bloom filters, SSTables, and sparse indexes in one read and write path. A relational engine may pair heap storage with B-trees and special-purpose indexes for text or geospatial access.

That mix explains many performance surprises. Slow reads may come from compaction debt, not from SQL itself. Slow writes may come from index maintenance rather than row storage. Once you know the structures underneath, database behaviour starts to look mechanical instead of mysterious.