B+ Дерева і Дерева LSM це дві основні структури даних, коли ми говоримо про будівельні блоки Бази даних. Дерева B+ використовуються, коли нам потрібно менше часу на пошук і вставку, а з іншого боку, дерева LSM використовуються, коли у нас є набори даних, які потребують інтенсивного запису, а кількість читань не така висока.

Ця стаття навчить про Структуроване дерево злиття журналу ака Дерево LSM . Дерева LSM — це структура даних, що лежить в основі багатьох розподілених баз даних типу «ключ-значення» з високою масштабованістю NoSQL, таких як DynamoDB, Cassandra та ScyllaDB від Amazon.

Дерева LSM

Проста версія LSM Trees містить 2 рівні деревоподібної структури даних:

• Memtable і повністю знаходиться в пам'яті (скажімо, T0)
• SStables, збережені на диску (скажімо, T1)

Просте дерево LSM

Нові записи вставляються в компонент memtable T0. Якщо вставка призводить до того, що компонент T0 перевищує певний поріг розміру, безперервний сегмент записів видаляється з T0 і об’єднується в T1 на диску.

Робочий процес LSM

LSM в основному використовує 3 концепції для оптимізації операцій читання та запису:

• Таблиця відсортованих рядків (SSTables) : Дані сортуються в порядку сортування, тому щоразу, коли дані зчитуються, їх часова складність буде O( Log(N)) у гіршому випадку, де N — це кількість записів у таблиці бази даних.

  1. SSTable

• Memtable :
  • Структура в пам'яті
  • Зберігає дані в сортованому вигляді
  • Діє як кеш зворотного запису
  • Після досягнення певного розміру його дані скидаються як SSTable до бази даних
  • Як, кількість SSTable збільшується на диску, і якщо якийсь ключ відсутній у записах
    • Під час читання цього ключа нам потрібно прочитати всі SSTables, що збільшує час читання.
    • Щоб подолати цю проблему, з’являється фільтр Bloom.
    • Фільтр Блума — це ефективна структура даних, яка може повідомити нам про відсутність ключа в наших записах із рівнем точності 99,9%.
    • Щоб використовувати цей фільтр, ми можемо додавати до нього наші записи, коли вони написані, і перевіряти ключ на початку запитів на читання, щоб ефективніше обслуговувати запити, коли вони надходять на перше місце.

Memtable подання

• Ущільнення :
  • Оскільки ми зберігаємо дані як SSTable на диску, скажімо, вони є Н SSTable і розмір кожної таблиці М
  • Тоді гірший випадок Прочитайте часова складність O( N* Log(M) )
  • Отже, оскільки кількість SSTables збільшується, Складність часу читання також збільшується.
  • Крім того, коли ми просто очищаємо SSTables у базі даних, той самий ключ присутній у кількох SSTables
  • Тут використовується компактор
  • Compactor працює у фоновому режимі, об’єднує SSTables і видаляє кілька рядків із тим самим, додає новий ключ із останніми даними та зберігає їх у новій об’єднаній/ущільненій SSTable.

3.1. SSTables скинуто на Диск

3.6. Компактор ущільнив 2 SSTables до 1 SSTtable

Висновок:

• Записи зберігаються в дереві пам’яті (Memtable). Будь-які допоміжні структури даних (фільтри розрідження та розріджений індекс) також оновлюються, якщо необхідно.
• Коли це дерево стає занадто великим, воно скидається на диск із ключами у відсортованому порядку.
• Коли надходить зчитування, ми перевіряємо його за допомогою фільтра Блюм. Якщо фільтр Блюм вказує, що значення відсутнє, ми повідомляємо клієнту, що ключ не знайдено. Якщо фільтр Блум означає, що значення присутнє, ми починаємо ітерацію SSTables від найновішої до найстарішої.
• Часові складності LSM
  • Час читання: O(log(N)) де N – кількість записів на диску
  • Час запису: О(1) як він записує в пам'яті
  • Час видалення: O(log(N)) де N – кількість записів на диску
• Дерева LSM можна модифікувати до більш ефективних структур даних за допомогою більше ніж 2 фільтрів. Деякі з них bLSM, Diff-Index LSM.