🌳 LSM-дерево в C#

LSM-дерево (Log-Structured Merge Tree) – одна из самых мощных структур для баз данных, кэширования и key-value хранилищ.

В отличие от B-деревьев, которые часто используются в реляционных БД, LSM-дерево отлично справляется с высоконагруженными системами благодаря журналированию и периодической компактификации данных.

Как работает LSM-дерево

1️⃣ Запись идёт в память (MemTable) – все операции сначала попадают в быстрое RAM-хранилище.

2️⃣ Данные записываются в WAL (Write-Ahead Log) – чтобы не потерять их при сбое.

3️⃣ Сброс в SSTables (Sorted String Tables) – периодически MemTable записывается на диск.

4️⃣ Компактификация – старые файлы объединяются, а удалённые ключи стираются.

Пример реализации в C#:

class LSMTree
{
    private SortedDictionary<string, string> memTable = new();
    private const string WAL_FILE = "wal.log";

    public LSMTree()
    {
        LoadFromWAL();
    }

    public void Put(string key, string value)
    {
        memTable[key] = value;
        File.AppendAllText(WAL_FILE, $"{key}:{value}\n");
    }

    public string Get(string key)
    {
        return memTable.TryGetValue(key, out var value) ? value : "Not found";
    }

    private void LoadFromWAL()
    {
        if (File.Exists(WAL_FILE))
        {
            foreach (var line in File.ReadAllLines(WAL_FILE))
            {
                var parts = line.Split(':');
                if (parts.Length == 2)
                    memTable[parts[0]] = parts[1];
            }
        }
    }
}

➖Где используется

• NoSQL базы данных: LevelDB, RocksDB, Cassandra

• Поисковые системы: Elasticsearch, Apache Lucene

• Хранилища для логов и кэшей

➖ Преимущества LSM-дерева

• Быстрая запись – все изменения сначала пишутся в память

• Эффективное хранение – используется сжатие и компактификация

• Масштабируемость – отлично работает при больших объёмах данных

➖ Но есть нюансы

• Медленный поиск — требуется слияние уровней

• Утилизация ресурсов — периодическая компактификация требует CPU

🔗 Как вы храните данные в своих проектах? Делитесь в комментариях! ⬇️

🐸Библиотека шарписта