20 May 2014

Файловое строение SQLite

SQLite
Translation
Original author: Официальный сайт
В данном посте база SQLite будет рассмотрена в разрезе, вы можете найти информацию о строении файла базы данных, о представлении данных в памяти, а также информацию о структуре и файловом представлении В – дерева.

Формат файла базы данных


Вся база данных хранится в одном файле на диске под названием «main database file». Во время транзакций, SQLite хранит дополнительную информацию во втором файле: журнал отката (rollback journal), либо, если база работает в режиме WAL, лог-файл с информацией о записях. Если приложение или компьютер отключился до окончания транзакции, то данные файлы называются «hot journal» или «hot WAL file» и содержат необходимую информацию для восстановления базы в согласованное состояние.

Страницы


Основной файл базы состоит из одной или нескольких страниц. Все страницы в одной базе имеют одинаковый размер, который может быть от 512 до 65536 байт. Размер страницы для файла базы определяется целым 2-ух байтовым числом со смещением 16 байт от начала файла базы данных.
Все страницы пронумерованы от 1 до 2147483646 (2^31 – 2). Минимальный размер базы: одна страница размеров 512 байт, максимальный размер базы: 2147483646 страниц по 65536 байт (~140 Тбайт).

Заголовок


Первый 100 байт файла базы данных содержат заголовок базы, в таблице 1 представлена схема заголовка.

Таблица 1

Lock-byte страница


Страница блокировки является одной страницей файла базы и находится между смещениями 0х1073741824 и 0х1073742335, если размер базы меньше, то она не имеет страницы блокировки. Данная страница нужна для реализации примитивов блокировки OS Interface’ом.

Freelist


Список пустых страниц организован как связный список. Каждый элемент списка состоит из двух чисел по 4 байта. Первое число определяет номер следующего элемента freelist (trunk pointer), либо равняется нулю, если список кончился. Второе число, это указатель на страницу данных (Leaf page numbers). На рисунке ниже показана схема данной структуры.



B — tree


SQLite использует две вида деревьев: «table B – tree» (на листьях хранятся данные) и «index B – tree» (на листьях хранятся ключи).
Каждая запись в «table B – tree» состоит из 64-битового целое ключа и до 2147483647 байт произвольных данных. Ключ «table B – tree» соответствует ROWID таблицы SQL.
Каждая запись в «index B – tree» состоит из произвольного ключа до 2147483647 байт в длину.

Страница B — tree


Страница B-дерева имеет структуру:
  • Заголовок файла базы данных (100 байт)
  • Заголовок страницы B-дерева (8 или 12 байт)
  • Массив указателей ячеек
  • Незанятое пространство
  • Содержимое ячейки
  • Зарезервированное место


Заголовок файла базы данных встречается только на первой странице, которая всегда является старицей «table B – tree». Все остальные страницы B-дерева в базе не имеют этого заголовка.

Заголовок страницы B-дерева имеет размер 8 байт для страниц листьев и 12 байт для внутренних страниц. В таблице 2 представлена структура заголовка страницы.
Таблица 2


Freeblock — это структура, используемая для определения незанятого пространства внутри страницы B-дерева. Freeblock организованы в виде цепочки. Первые 2 байта в freeblock (от старшего к младшему), это смещением до следующего freeblock, или ноль, если freeblock является последним в цепочке. Третий и четвертый байты – целое число, размер freeblock в байтах, включая заголовок в 4 байта. Freeblocks всегда связаны в порядке возрастания смещения.

Число фрагментированных байт – это общее число неиспользуемых байт в области содержимого ячейки.

Массив указателей ячеек состоит из K 2-байтовых целочисленных смещений содержимого ячеек (при K ячейках в B-дереве). Массив отсортирован по возрастанию (от наименьших ключей к наибольшим).

Незанятое пространство — это область между последней ячейкой массива указателей и началом первой ячейки.

Зарезервированное место в конце каждой страницы используется расширениями для хранения информации о странице. Размер зарезервированной области определяется в заголовке базы (по умолчанию равен нулю).

Representation


В данном разделе описана структура хранения данных в базе. Данные на листовых страницах table b — tree и ключи index b — tree, хранятся в качестве произвольной последовательности байт называемом record format (подробнее habrahabr.ru/post/223451).

TABLE


Каждая таблица (с ROWID) представляется в базе в виде table b — tree. Каждая запись в дереве, соответствует строке таблицы SQL. Одна строка SQL таблицы представляется в виде последовательности (той же что и указана при ее создании) столбцов таблицы в record format. Если таблица имеет INTEGER PRIMARY KEY, который является псевдонимом ROWID, то вместо его значения будет записано NULL. SQLite всегда будет использовать ключ table b — tree вместо значения NULL при обращении к INTEGER PRIMARY KEY. Если Affinity столбца (рекомендация приведения типа, подробнее habrahabr.ru/post/149635 в разделе «Типы данных и сравнение значений») является REAL и значение может быть преобразовано к INTEGER без потери данных, то значение будет хранится в виде целого числа. При извлечении данных из базы SQLite преобразует целое число к REAL.

TABLEWITHOUT ROWID


Каждая таблица (без ROWID) представляется в базе в виде index b — tree. Отличие от таблиц с rowid, заключается в том, что ключ каждой записи SQL таблицы хранится в виде record format, при чем столбцы ключа хранятся как указаны в PRIMARY KEY, а остальные в порядке указанном в объявлении таблицы.
Таким образом записи в index b — tree представляются также как и в table b — tree, кроме порядка столбцов и того, что содержание строки хранится в ключе дерева, а не в качестве данных на листьях как в table b — tree.

INDEX


Каждый индекс (объявленный CREATE INDEX, PRIMARY KEY или UNIQUE) представляется в базе в виду index b — tree. Каждая запись в таком дереве соответствует строки в SQL таблице. Ключ индексного дерева представляет собой последовательность значений столбцов указанных в индексе и завершается значением ключа строки (rowid или primary key) в record format.

UPD 13:44: переработан раздел Representation, спасибо за критику mayorovp (можно было конечно и пошевелиться, ну да ладно).
Tags:sqliteфайловая структураb-tree
Hubs: SQLite
+17
26.1k 110
Comments 21