Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni
🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!06.12.2024
Дев-адвент 6: внутрішня структура SQLite
Сьогодні часу не дуже багато було, тому задовольнився тим, що розібрався у внутрішній структурі SQLite, щоб зрозуміти її в контексті локальної бази даних, де сидітиме більшість даних застосунку. (До речі, в документації SQLite достатньо цікавих технічних деталей, щоб просто читати її для загального розвитку. Рекомендую.)
Щодо представлення записів (рядків таблиці): воно компактне, наскільки це можливо, та чимсь нагадує формати на кшталт msgpack. Для кожного значення відзначений свій тип, як памʼятаєте, але маркер типу складається з одного байту та навіть може містити в собі значення NULL, 0 та 1. Цілі числа зберігаються зі змінною шириною. В іншому, зрозумілий компактний формат, що інколи може бути важливо. Наприклад, JavaScript на ті ж дані витратить в рази більше памʼяті.
Щодо структури таблиць: тут все напрочуд просто та, на відміну від, наприклад, PostgreSQL, однозначно. Таблиця зберігається як Б-дерево. (Б-дерево це дерево, яке мінімізує свою висоту: тобто для БД, кількість вузлів-сторінок, за якими потрібно пройтися від кореня, щоб знайти запис.)
В кожного запису є ідентифікатор (rowid) - ціле число — та воно й використовується для побудови дерева. Цікаво, що якщо зробити ключем поле типу INTEGER PRIMARY KEY, то воно фактично й буде містити цей rowid, що пришвидшить пошук за ключем. (В іншому разі, спочатку потрібно знайти rowid за індексом, а потім вже запис за rowid.)
Індекси теж зберігаються як Б-дерева, з єдиною різницею, що тут вже значення в дереві можуть мати довільний тип, та це трохи ускладнює структуру даних. Індекси посилаються на rowid, тож в запитах, що поєднують декілька індексів, можливо фільтрувати записи ще за rowid , без завантаження.
Нарешті, в SQLite вся база даних міститься в одному файлі, він розбитий на сторінки (зазвичай по декілька КБ), та в памʼять можна завантажувати тільки ті, що потрібні. Що може стати дуже корисним, якщо даних багато, але ми не плануємо всі їх читати постійно.
Отже, що ми фактично отримуємо, порівняно зі збереженням даних в простих структурах в памʼяті? Прозорий спосіб заощадити на памʼяті (відвантаженням на диск), та також можливість швидко шукати з логарифмічною складністю — особливо за наявністю індексів.