<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Kushagar Lall on Medium]]></title>
        <description><![CDATA[Stories by Kushagar Lall on Medium]]></description>
        <link>https://medium.com/@kushagarlall1993?source=rss-44274790daba------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*iFeyQGY70SUKXLW9CLYSlw.jpeg</url>
            <title>Stories by Kushagar Lall on Medium</title>
            <link>https://medium.com/@kushagarlall1993?source=rss-44274790daba------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 07:18:49 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kushagarlall1993/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[B+ Trees: The Index Structure Behind Fast Range Queries]]></title>
            <link>https://medium.com/@kushagarlall1993/b-trees-the-index-structure-behind-fast-range-queries-84cab4db20fe?source=rss-44274790daba------2</link>
            <guid isPermaLink="false">https://medium.com/p/84cab4db20fe</guid>
            <dc:creator><![CDATA[Kushagar Lall]]></dc:creator>
            <pubDate>Wed, 09 Sep 2026 14:49:04 GMT</pubDate>
            <atom:updated>2026-09-09T14:56:03.945Z</atom:updated>
            <content:encoded><![CDATA[<p>When a database needs to find one record quickly, scan a range of records, or keep an index working as the dataset grows, the shape of its on-disk data structure matters.</p><p>A B+ tree is one of the most important structures used for this job. It keeps keys sorted, maintains a balanced height, and stores records in linked leaf nodes so that both point lookups and range scans remain efficient.</p><p>B+ trees are common in database indexes and file systems. They are especially useful when data lives on block storage, where minimizing the number of page reads is often more important than minimizing CPU instructions.</p><p><strong>The core idea</strong></p><p>A B+ tree is a balanced multi-way search tree with two types of nodes:</p><p>- <strong>**Internal nodes:**</strong> Store separator keys and pointers to child nodes.</p><p>- <strong>**Leaf nodes:**</strong> Store the actual keys and values. Leaf nodes are linked from left to right.</p><p>A simplified shape looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/1*973xS8pgrDuOvsNPNpcNOQ.png" /></figure><p>The internal keys guide navigation. The leaves contain the searchable data, and their linked-list connection makes ordered scans efficient.</p><p>Unlike a binary search tree, a B+ tree node can contain many keys and many children. This high fan-out keeps the tree shallow, which reduces the number of storage pages a lookup must read.</p><p><strong>Why databases use B+ trees</strong></p><p>Storage is usually accessed in pages or blocks rather than one byte at a time. A database wants each page read to provide as much useful index information as possible.</p><p>A binary tree with one key per node can become very tall. A B+ tree puts many keys in one page and therefore has a much smaller height.</p><p>For a tree with branching factor $M$ and $N$ indexed records, the height is approximately:</p><p>$$</p><p>O(\log_M N)</p><p>$$</p><p>Because $M$ can be large, a lookup may need only a few page reads even when the index contains millions of records.</p><p>The exact performance depends on page size, key size, pointer size, cache hit rate, and the distribution of keys. The important principle is high fan-out and bounded height.</p><p><strong>Searching for a key</strong></p><p>To search for a key, the database starts at the root and follows separator keys until it reaches a leaf.</p><p>Suppose the root contains `[30 | 60]`:</p><p>- keys smaller than `30` go to the first child;</p><p>- keys from `30` up to `60` go to the middle child;</p><p>- keys greater than or equal to `60` go to the last child.</p><p>The leaf is then searched for the exact key. Internal nodes do not need to store the full record value. They only need enough information to route the lookup.</p><p>A B+ tree lookup has two parts:</p><p>1. Navigate through internal nodes: approximately $O(\log_M N)$ node visits.</p><p>2. Search within the target leaf, using binary search or a small linear scan.</p><p>In practice, upper tree levels are often cached, so many requests need only one disk access to reach the leaf.</p><p><strong>Insertion</strong></p><p>Insertion follows a predictable sequence:</p><p>1. Navigate to the leaf where the key belongs.</p><p>2. Insert the key and value in sorted order.</p><p>3. If the leaf has room, stop.</p><p>4. If the leaf overflows, split it into two leaves.</p><p>5. Copy a separator key into the parent.</p><p>6. If the parent overflows, split the internal node too.</p><p>7. Continue splitting upward if necessary.</p><p>8. Create a new root if the old root splits.</p><p>A leaf split might look like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/446/1*up1WpZT5IvHVW5Nc_OXmoA.png" /></figure><p>The leaves retain the actual records. The parent receives a separator that helps route future searches. The separator is a routing key, not a second copy of the record.</p><p><strong>Internal-node splits</strong></p><p>Internal nodes contain keys and child pointers. When an internal node overflows, it is split into two nodes and one separator key moves upward into the parent.</p><p>This is different from a leaf split:</p><p>- a leaf split keeps all records in the leaves and copies a separator upward;</p><p>- an internal split promotes a separator and divides child pointers around it.</p><p>That distinction is a frequent interview question because confusing the two can lead to incorrect child counts or lost keys.</p><p><strong>Why the tree stays balanced</strong></p><p>B+ trees split nodes instead of allowing one path to grow deeper than another. Every leaf remains at the same depth.</p><p>This gives predictable lookup cost. Inserting a key may cause local work and, in the worst case, a chain of splits up to the root, but the tree never becomes a long, skewed chain like an ordinary binary search tree can.</p><p>Deletion uses the reverse ideas:</p><p>1. Remove the key from its leaf.</p><p>2. If the node still has enough entries, stop.</p><p>3. Otherwise borrow from a sibling when possible.</p><p>4. If borrowing is not possible, merge with a sibling.</p><p>5. Update separator keys in the parent.</p><p>6. Continue upward if the parent underflows.</p><p>Deletion is more involved than insertion because it must preserve minimum occupancy and routing correctness.</p><p><strong>Range queries are where B+ trees shine</strong></p><p>Point lookup is only half the story. Consider this query:</p><p>SELECT * FROM orders</p><p>WHERE customer_id = 42</p><p>AND created_at &gt;= ‘2026–01–01’</p><p>AND created_at &lt; ‘2026–02–01’;</p><p>After finding the first matching leaf, the database can follow the leaf-level links and scan neighboring records in key order. It does not need to return to the root for every next key.</p><p>This makes B+ trees a strong fit for:</p><p>- range queries;</p><p>- ordered iteration;</p><p>- prefix scans when the index key supports them;</p><p>- finding the minimum or maximum key;</p><p>- pagination over a sorted index.</p><p>The index key order determines which range queries are efficient. A composite index such as `(customer_id, created_at)` can support the example query because records for the same customer are adjacent in key order.</p><p><strong>B+ trees and database pages</strong></p><p>A production B+ tree usually maps closely to fixed-size pages:</p><p>page id -&gt; page contents</p><p>An internal page contains separator keys and child page identifiers. A leaf page contains index entries or, depending on the index type, pointers to table rows.</p><p>A page may also contain metadata such as:</p><p>- the page identifier;</p><p>- the parent identifier;</p><p>- the number of valid entries;</p><p>- sibling page identifiers;</p><p>- a checksum or version;</p><p>- free-space information.</p><p>The tree is not necessarily held entirely in memory. A buffer pool loads pages as needed, pins pages while they are being used, and writes dirty pages back to storage according to the database’s recovery rules.</p><p><strong>Clustered and secondary indexes</strong></p><p>A B+ tree can organize the table’s rows directly, or it can act as a secondary index.</p><p>In a clustered index, leaf entries contain the row data or are arranged in the table’s primary-key order. This makes lookups and ranges on that key efficient, but inserting rows may cause page splits and affect physical layout.</p><p>In a secondary index, leaf entries usually contain the indexed key plus a row identifier. The database finds the index entry first and then performs another lookup to retrieve the full row.</p><p>This distinction matters because an index can make finding rows faster while still requiring additional random lookups for the row data.</p><p><strong>The tradeoffs</strong></p><p>B+ trees are not automatically better than every alternative. Hash indexes can be excellent for exact-match lookups. LSM trees often provide higher write throughput for write-heavy workloads by turning updates into sequential writes and handling organization through compaction.</p><p><strong>Interview mental model</strong></p><p>When explaining a B+ tree in an interview, cover this sequence:</p><p>1. Internal nodes route searches; leaves store the actual entries.</p><p>2. Each node holds many keys, giving the tree high fan-out.</p><p>3. All leaves stay at the same depth.</p><p>4. Leaf nodes are linked for efficient range scans.</p><p>5. Inserts split overflowing leaves and propagate separators upward.</p><p>6. Internal splits may continue to the root, creating a new root if needed.</p><p>7. Deletes borrow from or merge with siblings to preserve occupancy.</p><p>8. On disk, nodes usually correspond to pages managed by a buffer pool.</p><p>Then discuss the engineering details: page size, cache behavior, clustered versus secondary indexes, concurrency during splits, WAL/recovery, and the difference between point lookups and range scans.</p><p><strong>A code starting point for interview preparation</strong></p><p>Use it to trace the main concepts:</p><pre>public class BPlusTree<br>{<br>    abstract class Node<br>    {<br>        List&lt;Integer&gt; keys = new ArrayList&lt;&gt;();<br>        Node parent;<br><br>        abstract boolean isLeaf();<br>    }<br><br>    public class InternalNode extends Node<br>    {<br>        public List&lt;Node&gt; children = new ArrayList&lt;&gt;();<br>        public boolean isLeaf()<br>        {<br>            return false;<br>        }<br>    }<br><br>    public class LeafNode extends Node<br>    {<br>        public List&lt;Integer&gt; values = new ArrayList&lt;&gt;();<br>        public LeafNode next;<br><br>        public boolean isLeaf()<br>        {<br>            return true;<br>        }<br>    }<br><br>    private Node root;<br>    private static final int M = 4; // or the order defines the max num children each node can have<br><br>    public BPlusTree()<br>    {<br>        root = new LeafNode();<br>    }<br><br>    public Integer search(int key)<br>    {<br>        LeafNode leafNode = findLeafNode(root, key);<br>        for (int i = 0; i &lt; leafNode.keys.size(); i++)<br>        {<br>            if(leafNode.keys.get(i) == key)<br>            {<br>                return leafNode.values.get(i);<br>            }<br>        }<br>        return null;<br>    }<br><br>    public void insert(int key, int value)<br>    {<br>        // find the leaf where this key needs to be inserted<br>        LeafNode leafNode = findLeafNode(root , key);<br>        // get the index where we can insert the value<br>        int idx = Collections.binarySearch(leafNode.keys, key);<br>        if(idx &gt;= 0)<br>        {<br>            leafNode.values.set(idx, value);<br>        }<br><br>        idx = -idx-1;<br>        leafNode.keys.add(idx, value);<br>        leafNode.values.add(idx , value);<br><br>        if(leafNode.keys.size() &gt; M-1)<br>        {<br>            // split the current leaf node<br>            splitLeafNode(leafNode);<br>        }<br>    }<br><br>    private LeafNode findLeafNode(Node node , int key)<br>    {<br>        while (!node.isLeaf())<br>        {<br>            InternalNode internalNode = (InternalNode) node;<br>            int i = 0;<br>            while(i &lt; internalNode.keys.size() &amp;&amp; key &gt;= internalNode.keys.get(i))<br>            {<br>                i++;<br>            }<br>            node = ((InternalNode) node).children.get(i);<br>        }<br>        return (LeafNode) node;<br>    }<br><br>    private void splitLeafNode(LeafNode leaf)<br>    {<br>        LeafNode newLeaf = new LeafNode();<br>        int mid = (M+1)/2;<br><br>        // split the leafNode , dividing half the nodes into one and other half into another<br>        newLeaf.keys.addAll(leaf.keys.subList(mid,leaf.keys.size()));<br>        leaf.values.subList(mid, leaf.values.size()).clear();<br><br>        newLeaf.next = leaf.next;<br>        leaf.next = newLeaf;<br><br>        insertParent(leaf, newLeaf.keys.get(0), newLeaf);<br>    }<br><br>    private void insertParent(Node left, int key, Node right)<br>    {<br>        if(left == root)<br>        {<br>            InternalNode newRoot = new InternalNode();<br>            newRoot.keys.add(key);<br>            newRoot.children.add(left);<br>            newRoot.children.add(right);<br>            return;<br>        }<br><br>        InternalNode parent = (InternalNode) left.parent;<br>        int idx = parent.children.indexOf(left)+1;<br>        parent.keys.add(idx-1, key);<br>        parent.children.add(idx , right);<br><br>        right.parent = parent;<br><br>        if(parent.children.size() &gt; M)<br>        {<br>            splitInternalNode(parent);<br>        }<br>    }<br><br>    private void splitInternalNode(InternalNode node)<br>    {<br>        int mid = node.keys.size()/2;<br><br>        int pushUpKey = node.keys.get(mid);<br><br>        InternalNode rightNode = new InternalNode();<br>        rightNode.keys.addAll(node.keys.subList(mid+1, node.keys.size()));<br>        rightNode.children.addAll(node.children.subList(mid+1, node.keys.size()));<br><br>        for(Node child : rightNode.children)<br>        {<br>            child.parent = rightNode;<br>        }<br><br>        node.keys.subList(mid , node.keys.size()).clear();<br>        node.children.subList(mid+1 , node.children.size()).clear();<br><br>        insertParent(node, pushUpKey, rightNode);<br>    }<br><br>    public void printTree()<br>    {<br>        Queue&lt;Node&gt; queue = new LinkedList&lt;&gt;();<br>        queue.add(root);<br><br>        // bfs<br>        while (!queue.isEmpty())<br>        {<br>            int cnt = queue.size();<br>            for (int i = 0; i &lt; cnt; i++)<br>            {<br>                Node node = queue.poll();<br>                System.out.println(node.keys + &quot; &quot;);<br>                if(!node.isLeaf())<br>                {<br>                    queue.addAll(((InternalNode) node).children);<br>                }<br>            }<br>            System.out.println();<br>        }<br>    }<br>}</pre><p>- internal nodes and leaf nodes;</p><p>- parent pointers;</p><p>- leaf-to-leaf links;</p><p>- search navigation;</p><p>- leaf splitting;</p><p>- internal-node splitting;</p><p>- separator propagation.</p><p>It is a learning scaffold rather than a production B+ tree. Good exercises include fixing duplicate-key insertion, correctly assigning a new root after a root split, preserving values during leaf splits, maintaining every child parent pointer, implementing deletion, and adding tests for point and range queries.</p><p>The concepts are the important part of the interview discussion. The code gives you a compact place to make those concepts concrete and extend the implementation one invariant at a time.</p><p>Next steps here would be to see how sql uses it. A very important concept that i find useful regarding sql , how to scale :</p><p><a href="https://learn.microsoft.com/en-us/sql/odbc/reference/develop-app/transaction-isolation-levels?view=sql-server-ver16">https://learn.microsoft.com/en-us/sql/odbc/reference/develop-app/transaction-isolation-levels?view=sql-server-ver16</a></p><p><a href="https://learn.microsoft.com/en-us/sql/relational-databases/partitions/partitioned-tables-and-indexes?view=sql-server-ver16">https://learn.microsoft.com/en-us/sql/relational-databases/partitions/partitioned-tables-and-indexes?view=sql-server-ver16</a></p><p><a href="https://learn.microsoft.com/en-us/sql/relational-databases/stored-procedures/create-a-stored-procedure?view=sql-server-ver17">https://learn.microsoft.com/en-us/sql/relational-databases/stored-procedures/create-a-stored-procedure?view=sql-server-ver17</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=84cab4db20fe" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LSM Trees: The Data Structure Behind Fast Writes]]></title>
            <link>https://medium.com/@kushagarlall1993/lsm-trees-the-data-structure-behind-fast-writes-d34a3151be68?source=rss-44274790daba------2</link>
            <guid isPermaLink="false">https://medium.com/p/d34a3151be68</guid>
            <category><![CDATA[lsm-tree]]></category>
            <category><![CDATA[distributed-design]]></category>
            <category><![CDATA[database]]></category>
            <dc:creator><![CDATA[Kushagar Lall]]></dc:creator>
            <pubDate>Thu, 03 Sep 2026 15:32:34 GMT</pubDate>
            <atom:updated>2026-09-03T15:54:32.155Z</atom:updated>
            <content:encoded><![CDATA[<p><strong># LSM Trees: How Modern Databases Make Writes Fast</strong></p><p>Many databases need to accept a continuous stream of writes while keeping reads reasonably fast and data durable. The challenge is that storage devices are much better at sequential I/O than random I/O.</p><p>Updating a traditional on-disk index in place can turn every logical write into several physical operations: find the page, modify it, split it if necessary, and write it back. At scale, those random updates create contention, write amplification, and unpredictable latency.</p><p>An LSM tree takes a different approach:</p><p>&gt; Write new data sequentially, organize it in memory, and merge it in the background.</p><p>This design is called a <strong>**Log-Structured Merge tree**</strong>, or <strong>**LSM tree**</strong>. It is not a single tree-shaped data structure in the usual sense. It is a collection of in-memory and on-disk structures, together with background processes that keep them manageable.</p><p>LSM-based storage engines are used in systems such as LevelDB, RocksDB, and Cassandra. Many other databases use similar ideas, although the details of their file formats, consistency models, and compaction strategies differ.</p><p><strong>The high-level architecture</strong></p><p>An LSM storage engine usually contains these layers:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/725/1*dLXyCZtCLvHseeJNVg7o9A.png" /></figure><p>The main components are:</p><p>- <strong>**Write-ahead log (WAL):**</strong> An append-only log used to recover recent writes after a crash.</p><p>- <strong>**Memtable:**</strong> A mutable, in-memory ordered table containing the latest writes that have not yet been flushed.</p><p>- <strong>**SSTable:**</strong> An immutable, sorted string table stored on disk.</p><p>- <strong>**Compaction:**</strong> Background work that merges SSTables, removes obsolete versions, and controls the number of files.</p><p>The word “merge” in LSM refers to this repeated merging of sorted runs. The system does not repeatedly update one large file in place. It creates new sorted runs and merges them later.</p><p><strong>The write path</strong></p><p>Consider a write such as:</p><p>user:42 -&gt; {name: “Maya”, plan: “pro”}</p><p>The database generally handles it in this order:</p><p>1. Append the operation to the WAL.</p><p>2. Update the memtable.</p><p>3. Acknowledge the write according to the configured durability policy.</p><p>4. Flush the memtable to a new immutable SSTable when it reaches its size limit.</p><p>5. Compact SSTables in the background.</p><p>The WAL protects against process failure. The memtable makes recent reads fast. The flush turns a batch of updates into a sequential disk write.</p><p><strong>WAL durability is a policy</strong></p><p>It is tempting to say that “the WAL makes the write durable,” but that statement needs qualification. A database may acknowledge a write after:</p><p>- appending it to an application buffer;</p><p>- flushing it to the operating system;</p><p>- forcing it to stable storage with an `fsync`-like operation;</p><p>- replicating it to other nodes.</p><p>These policies offer different latency and failure guarantees. A small educational implementation can demonstrate WAL ordering, but production systems need explicit control over flushing, checksums, torn writes, and recovery of partial records.</p><p><strong>Memtables and immutable SSTables</strong></p><p>The memtable is usually an ordered structure such as a skip list, balanced tree, or another specialized in-memory index. Ordering matters because it lets the engine produce sorted output during a flush.</p><p>An SSTable is immutable and sorted by key. Immutability has useful consequences:</p><p>- readers do not compete with writers modifying the same file;</p><p>- files can be checksummed and safely shared across processes or replicas;</p><p>- sequential writes are easier to perform efficiently;</p><p>- compaction can create a new file before replacing old metadata.</p><p>A flushed SSTable can contain a key that already exists in an older SSTable. That is expected. LSM engines usually treat records as versions of a key and rely on read ordering and compaction to resolve them.</p><p><strong>The read path</strong></p><p>A point lookup typically checks data from newest to oldest:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/312/1*SyIYxwK6v_VJA808NFz_NA.png" /></figure><p>If a key exists in multiple layers, the first visible version wins. This is why the ordering of SSTables is a correctness rule, not only a performance optimization.</p><p>The naive read path could scan every record in every SSTable. That would quickly become too slow, so real engines use several structures to avoid unnecessary work.</p><p><strong>Index blocks</strong></p><p>An SSTable is divided into blocks. A sparse index maps key ranges to block locations. Instead of scanning the entire file, a lookup can find the likely block and then search within it.</p><p>The index does not necessarily contain every key. It provides enough information to narrow the search while keeping the index small.</p><p><strong>Bloom filters</strong></p><p>A Bloom filter answers a useful question:</p><p>&gt; Is this key definitely absent from this SSTable?</p><p>If the filter says “absent,” the engine can skip the file. If it says “present,” the key may still be absent because Bloom filters can produce false positives, but they do not produce false negatives when implemented correctly.</p><p>Bloom filters are especially valuable when a database has many SSTables and the requested key is usually absent from most of them.</p><p><strong>Block cache</strong></p><p>Frequently accessed SSTable blocks can be retained in memory. This avoids repeatedly reading the same disk blocks and makes hot-key workloads much faster.</p><p>Together, indexes, Bloom filters, and caching reduce the read cost created by the append-and-merge write strategy.</p><p><strong>Updates, deletes, and versions</strong></p><p>LSM storage is commonly append-oriented, so an update does not need to find and overwrite the old value immediately. The database writes a newer record for the same key.</p><p>Deletes work similarly. The engine writes a <strong>**tombstone**</strong>, a marker saying that a key has been deleted. The old value cannot be removed immediately because an older SSTable or an active snapshot may still need it.</p><p>During compaction, the engine can remove an old value and its tombstone only when it knows that no required reader or lower-level file can observe them. This is one reason compaction is part of the correctness story, not merely a storage optimization.</p><p><strong>Compaction: the essential background process</strong></p><p>Without compaction, every memtable flush would create another SSTable. Reads would need to check more files, deleted data would remain forever, and disk usage would grow unnecessarily.</p><p>Compaction merges sorted SSTables into a new sorted SSTable. As it does so, it can:</p><p>- keep only the newest version of a key;</p><p>- preserve tombstones until it is safe to discard them;</p><p>- combine small files into larger files;</p><p>- rebuild indexes and Bloom filters;</p><p>- reclaim space occupied by obsolete records.</p><p>The result is similar to merging sorted arrays. Because the input files are already sorted, the engine can merge them efficiently with sequential reads and writes.</p><p><strong>LSM trees versus B-trees</strong></p><p>Neither LSM trees nor B-trees are universally better. They optimize for different costs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/760/1*dZcuRfFkW0eX5ZbBjeWwtQ.png" /></figure><p>The right choice depends on access patterns, storage hardware, latency targets, workload mix, and operational constraints.</p><p><strong>Where LSM trees fit in modern databases</strong></p><p>LSM trees are particularly attractive when a system has:</p><p>- a high rate of inserts or updates;</p><p>- append-friendly storage;</p><p>- workloads where sequential I/O is valuable;</p><p>- data that can be organized and compacted asynchronously;</p><p>- a need to scale writes across partitions or nodes.</p><p>Distributed databases add another dimension: each partition may have its own LSM engine, while replication, consistency, and repair happen above or alongside the storage layer. The LSM tree improves local write behavior, but it does not by itself solve distributed consensus, replication, transactions, or query planning.</p><p>That distinction matters in interviews. An LSM tree is a storage-engine technique, not a complete database architecture.</p><p><strong>Interview mental model</strong></p><p>When explaining an LSM tree, walk through this sequence:</p><p>1. A write is appended to a WAL for recovery.</p><p>2. The latest value is placed in an in-memory ordered memtable.</p><p>3. A full memtable is flushed as an immutable sorted SSTable.</p><p>4. Reads search the newest layers first.</p><p>5. Indexes, Bloom filters, and caches reduce read amplification.</p><p>6. Compaction merges files and removes obsolete versions and tombstones.</p><p>7. The system trades foreground write cost for background CPU, I/O, and space.</p><p>Then discuss the workload-dependent tradeoffs: write amplification, read amplification, space amplification, compaction stalls, durability policy, and snapshot behavior.</p><p><strong>A code starting point for interview preparation</strong></p><p>The code contains a small educational implementation.</p><pre>class SSTable<br>{<br>    private final String fileName;<br>    private final List&lt;Map&lt;String, String&gt;&gt; data;<br><br>    public SSTable(String fileName)<br>    {<br>        this.fileName = fileName;<br>        this.data = loadSSTable();<br>    }<br><br>    private List&lt;Map&lt;String,String&gt;&gt; loadSSTable()<br>    {<br>        List&lt;Map&lt;String,String&gt;&gt; dataRecords = new ArrayList&lt;&gt;();<br>        java.io.File file = new java.io.File(this.fileName);<br>        if(!file.exists())<br>        {<br>            return dataRecords;<br>        }<br><br>        try (BufferedReader br = new BufferedReader(new FileReader(file))) {<br>            // read file here and insert to the data-records list<br>            String line;<br>            while ((line = br.readLine()) != null)<br>            {<br>                Map&lt;String,String&gt; entry = new HashMap&lt;&gt;();<br>                String[] parts = line.split(&quot;,&quot;, 2);<br>                if (parts.length != 2) continue;<br>                entry.put(&quot;key&quot;, parts[0]);<br>                entry.put(&quot;value&quot;, parts[1]);<br>                dataRecords.add(entry);<br>            }<br>        } catch (FileNotFoundException e) {<br>            throw new RuntimeException(e);<br>        } catch (IOException e) {<br>            throw new RuntimeException(e);<br>        }<br>        return dataRecords;<br>    }<br><br>    public String get(String key) {<br>        // before searching we can add bloom filter here<br>        for (Map&lt;String, String&gt; entry : data) {<br>            if (entry.get(&quot;key&quot;).equals(key)) { // binary search since we are putting records sorted by key<br>                return entry.get(&quot;value&quot;);<br>            }<br>        }<br>        return null;<br>    }<br><br>    //writeSSTable(String fileName , List&lt;Pair&lt;String,String&gt;&gt; data)<br>    public static void writeSSTable(String filename, List&lt;Map&lt;String, String&gt;&gt; data)<br>    {<br>        try (BufferedWriter bw = new BufferedWriter(new FileWriter(filename))) {<br>            for (Map&lt;String, String&gt; entry : data) {<br>                bw.write(entry.get(&quot;key&quot;) + &quot;,&quot; + entry.get(&quot;value&quot;) + &quot;\n&quot;);<br>            }<br>        } catch (IOException e) {<br>            e.printStackTrace();<br>        }<br>    }<br>}<br><br>public class LSM<br>{<br>    private final TreeMap&lt;String,String&gt; memTable;<br>    private final String walFile = &quot;wal.log&quot;;<br>    private final String ssTableDir = &quot;ssTables/&quot;;<br>    private final List&lt;SSTable&gt; ssTableList;<br><br>    public LSM()<br>    {<br>        memTable = new TreeMap&lt;&gt;();<br>        ssTableList = new ArrayList&lt;&gt;();<br>        new java.io.File(ssTableDir).mkdirs();<br>        loadSSTables();<br>        loadWAL();<br>    }<br><br>    private void loadWAL() {<br>        java.io.File file = new java.io.File(walFile);<br>        if (!file.exists()) return;<br>        try (BufferedReader br = new BufferedReader(new FileReader(file))) {<br>            String line;<br>            while ((line = br.readLine()) != null) {<br>                String[] parts = line.split(&quot;,&quot;, 2);<br>                if (parts.length != 2) continue;<br>                memTable.put(parts[0], parts[1]);<br>            }<br>        } catch (IOException e) {<br>            e.printStackTrace();<br>        }<br>    }<br><br>    private void loadSSTables() {<br>        java.io.File dir = new java.io.File(ssTableDir);<br>        java.io.File[] files = dir.listFiles((d, name) -&gt; name.endsWith(&quot;.sst&quot;));<br>        if (files != null) {<br>            Arrays.sort(files, Comparator.comparing(java.io.File::getName).reversed());<br>            for (java.io.File file : files) {<br>                ssTableList.add(new SSTable(file.getAbsolutePath()));<br>            }<br>        }<br>    }<br><br>    public void put(String key , String val)<br>    {<br>        //put to the memtable and wal<br>        try(BufferedWriter bw = new BufferedWriter(new FileWriter(walFile,true))) {<br>            bw.write(key + &quot;,&quot; + val + &quot;\n&quot;);<br>        } catch (IOException e) {<br>            throw new RuntimeException(e);<br>        }<br>        // first put to wal if the node crashes before this our data is safe on disk<br>        memTable.put(key,val);<br>    }<br><br>    public String get(String key) {<br>        //first find the record in the memtable<br>        if (memTable.containsKey(key)) {<br>            return memTable.get(key);<br>        }<br>        //if not present in memtable search for all the sstables , this searching can be improved further if sstable had index on it<br>        for (SSTable sstable : ssTableList) {<br>            String value = sstable.get(key);<br>            if (value != null) {<br>                return value;<br>            }<br>        }<br>        return null;<br>    }<br><br>    public void flush()<br>    {<br>        // put all the entries present in the mem-table into an immutable object called sstable<br>        // we call this only when the ram is getting full and can&#39;t have the memtable in memory<br>        if (memTable.isEmpty()) return;<br>        List&lt;Map&lt;String, String&gt;&gt; sortedData = new ArrayList&lt;&gt;();<br>        for (Map.Entry&lt;String, String&gt; entry : memTable.entrySet()) {<br>            Map&lt;String, String&gt; map = new HashMap&lt;&gt;();<br>            map.put(&quot;key&quot;, entry.getKey());<br>            map.put(&quot;value&quot;, entry.getValue());<br>            sortedData.add(map);<br>        }<br>        sortedData.sort(Comparator.comparing(o -&gt; o.get(&quot;key&quot;)));<br>        String filename = ssTableDir + &quot;sstable_&quot; + (ssTableList.size() + 1) + &quot;.sst&quot;;<br>        SSTable.writeSSTable(filename, sortedData);<br>        ssTableList.add(0, new SSTable(filename));<br>        memTable.clear();<br>        new java.io.File(walFile).delete();<br>    }<br>}</pre><p>Use it as a starting point rather than as a production design.</p><p>The useful exercises are to trace the WAL, memtable, SSTable flush, and newest-first lookup, then extend the implementation with:</p><p>- recovery tests;</p><p>- a real SSTable index;</p><p>- a Bloom filter;</p><p>- tombstones and deletes;</p><p>- compaction;</p><p>- concurrency control;</p><p>- checksums and crash-safe file replacement.</p><p>The concepts above are the important part of the interview discussion. The code gives you a compact place to make those concepts concrete and explore the tradeoffs one feature at a time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d34a3151be68" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>