Others

• SSTables, Sorted String Tables
• LSM (Log Structured Merge Trees)
• Bitmap
• Large Objects

Eight Key Data Structures That Power Modern Databases

• Skiplist: a common in-memory index type. Used in Redis
• Hash index: a very common implementation of the “Map” data structure (or “Collection”)
• SSTable: immutable on-disk “Map” implementation
• LSM tree: Skiplist + SSTable. High write throughput
• B-tree: disk-based solution. Consistent read/write performance
• Inverted index: used for document indexing. Used in Lucene
• Suffix tree: for string pattern search
• R-tree: multi-dimension search, such as finding the nearest neighbor