Yash Mittal

3 - Storage & Retrieval

3 min read

  • Sorted String Tables (SSTables)

  • Maintaining sorted order of data is simpler in memory, we can use any balanced tree (Red-Black, AVL etc.) which will allow us to insert the data in any order but read it back in a sorted order always.

    • These in-memory trees are called memtables

  • Log Structure Merge Trees (LSM Trees)

    • Storage engines that work on this principle of merging and compacting stored files are called LSM based engines
    • Lucene the indexing system used in ElasticSearch is also based on LSM Trees where the index (which is the word) is the key and the value is the list of IDs of documents where that word appears, these indexes are compacted and merged in the BG as and when required.
    • LSM Trees are inherently slower in searching for keys that don’t exist (they’ll search for everything and then say nothing exists — this is where the Bloom Filter shines since despite being a probablistic DS it can be sure of negative set memberships.)
    • LSM Trees are write optimised

  • B-Trees

    • Most commonly used Index Implementations in Relational DBs
    • B-Trees have a very good distinction from the LSM Trees and that is the process of overriding pages, since BTrees mostly store pointers to pages, they override the page without changing it’s reference keeping the structure intact and searches reliable, an LSM Tree on the other hand just appends merges and deletes, i.e. it changes page references but never overrides
    • A 4 level BTree with 4KB page size can store 256TB of data
    • Write Ahead Log (WAL) is used to make databases resilient to crashes
      • What you do in a write ahead log is just write every operation before applying it to the tree — this makes sure that if the DB/System crashes mid update you can construct it back up
      • this is similar to how we can fix a memtable as well, we maintain a append only file for a memtable from which it can be reconstructed in case of a failure
    • B-Trees are Read Optimised

  • Secondary Indexes

    • Indexes is the key which a query searches for
    • B-Trees or LSM Trees can be used to implement them
    • The result could either be the row itself or it could be a reference to a heap file which helps to reduce data duplication incase of multiple indices and keep the data in a single place
    • clustered index help prevent the hop from heap file locations by storing the row directly

  • Transaction Processing

  • Online Transaction Processing (OLTP) - Where the user queries some data and gets the entire row back via some index

  • Online Analytics Processing (OLAP) - Where the user queries some data to read and aggregate a couple columns

Graph View