Формат файла SQLite

SQLite предлагает эффективное хранение данных, так как может сохранять всю информацию о базе данных в одном файле, что облегчает проектирование и оптимизацию производительности, ведь знание структуры файла помогает лучше использовать возможности движка

Основной файл базы данных

Полное состояние базы данных SQLite обычно содержится в одном файле на диске, который называется «основным файлом базы данных»

Во время транзакции SQLite записывает дополнительную информацию во вторичный файл, называемый «журналом отката» (rollback journal) или, если включено использование режима WAL (write-ahead log), в файл журнала с упреждающей записью

Горячие журналы

В случае неожиданного завершения работы приложения или компьютера до окончания транзакции, журнал отката или WAL-файл сохраняют необходимые данные для восстановления базы в корректное состояние. Эти журналы, известные как «горячие», важны для обеспечения целостности данных, хотя сбои случаются редко

Страницы

Основной файл базы данных состоит из одной или нескольких страниц, каждая из которых имеет размер, представляющий степень двойки в диапазоне от 512 до 65536. Размер страницы определяется 2-байтовым целым числом по смещению 16 байт от начала файла базы данных

Нумерация страниц начинается с 1, причем максимальный номер страницы составляет 4294967294 (2³² − 2). Минимальный размер базы данных SQLite — одна страница размером 512 байт. Максимальный теоретический размер базы данных мог бы составить 4294967294 страницы по 65536 байт, что эквивалентно 281474976579584 байтам (около 281 терабайта), но на практике ограничения файловой системы или диска чаще становятся критическими раньше

В обычном использовании размер баз данных SQLite варьируется от нескольких килобайт до нескольких гигабайт, хотя известно, что базы данных SQLite размером в терабайты существуют в производственной среде

В любой момент времени каждая страница основной базы данных имеет единственное назначение, которое является одним из следующих:

• Страница b-дерева — внутренняя страница b-дерева таблицы
• Страница b-дерева — листовая страница b-дерева таблицы
• Страница b-дерева — внутренняя страница b-дерева индекса
• Страница b-дерева — листовая страница b-дерева индекса
• Страница свободного списка — страница-ствол свободного списка (freelist trunk page)
• Страница свободного списка — листовая страница свободного списка (freelist leaf page)
• Страница переполнения полезной нагрузки (payload overflow page)
• Страница карты указателей (pointer map page)
• Страница блокировочного байта (lock-byte page)

Все операции чтения и записи в основной файл базы данных происходят на границе страниц, при этом все операции записи имеют размер, кратный количеству страниц. Чтение также может быть кратным размеру страниц, кроме первого считывания, когда первые 100 байт файла базы данных (заголовок) обрабатываются как единое целое

По этой теме полезно отдельно посмотреть EXPLAIN QUERY PLAN: план выполнения SQL-запроса в SQLite, чтобы расширить контекст и сравнить подходы

По этой теме полезно отдельно посмотреть Создание Flutter-приложения с SQLite, BLoC и Streams, чтобы расширить контекст и сравнить подходы

Заголовок базы данных

Первые 100 байт файла базы данных определяют заголовок файла. Заголовок включает несколько полей, как указано в соответствующей таблице

Магическая строка заголовка

Каждый корректный файл базы данных SQLite начинается с 16 байт (шестнадцатерично: 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00), что соответствует строке UTF-8 "SQLite format 3", включая нулевой символ-терминатор

Размер страницы

Значение, начиная с смещения 16, указывает размер страницы базы данных. Для версий SQLite 3.7.0.1 и более ранних это значение интерпретируется как целое число в формате big-endian, представляющее степень двойки от 512 до 32768. С версии SQLite 3.7.1 поддерживается размер страницы 65536 байт, что обозначается специальным кодом

Номера версий формата файла

Версии формата файла для записи и чтения, расположенные по смещениям 18 и 19, предназначены для будущего расширения. В текущих версиях SQLite оба значения равны 1 для журналов с откатом и 2 для WAL. Если файл базы данных с версией для чтения равен 1 или 2 и версия для записи больше 2, он должен быть доступен только для чтения

Зарезервированные байты на страницу

SQLite имеет возможность резервировать небольшое количество дополнительных байт в конце каждой страницы для использования расширениями. Эти дополнительные байты используются, например, расширением SQLite Encryption Extension для хранения одноразового числа (nonce) и/или криптографической контрольной суммы, связанной с каждой страницей

Размер «зарезервированного пространства» в 1-байтовом целом числе по смещению 20 — это количество байт пространства в конце каждой страницы, зарезервированных для расширений. Это значение обычно равно 0. Значение может быть нечётным

«Используемый размер» страницы базы данных — это размер страницы, указанный 2-байтовым целым числом по смещению 16 в заголовке, за вычетом размера «зарезервированного» пространства, записанного в 1-байтовом целом числе по смещению 20 в заголовке. Используемый размер страницы может быть нечётным числом. Однако используемый размер не может быть меньше 480

Иными словами, если размер страницы равен 512, то размер зарезервированного пространства не может превышать 32

Доли полезной нагрузки

Максимальная и минимальная доли встроенной полезной нагрузки и значение доли полезной нагрузки листа должны быть равны 64, 32 и 32 соответственно. Изначально эти значения предполагались настраиваемыми параметрами, которые можно было бы использовать для изменения формата хранения алгоритма b-дерева. Однако эта функциональность не поддерживается, и в настоящее время нет планов по добавлению такой поддержки в будущем. Поэтому эти три байта зафиксированы на указанных значениях

Счётчик изменений файла

Счётчик изменений файла — это 4-байтовое целое число в формате big-endian по смещению 24, которое увеличивается каждый раз, когда файл базы данных разблокируется после изменения. Когда два или более процессов читают один и тот же файл базы данных, каждый процесс может обнаруживать изменения базы данных, внесённые другими процессами, отслеживая счётчик изменений

Обычно процесс захочет сбросить кэш страниц базы данных, когда другой процесс изменил базу данных, поскольку кэш устарел. Счётчик изменений файла обеспечивает эту возможность

В режиме WAL изменения в базе данных обнаруживаются с помощью wal-index, поэтому счётчик изменений не нужен. Следовательно, счётчик изменений может не увеличиваться при каждой транзакции в режиме WAL

Размер базы данных в заголовке

4-байтовое целое число в формате big-endian по смещению 28 в заголовке хранит размер файла базы данных в страницах. Если этот размер базы данных в заголовке недействителен (см. следующий абзац), то размер базы данных вычисляется путём просмотра фактического размера файла базы данных. Более старые версии SQLite игнорировали размер базы данных в заголовке и использовали исключительно фактический размер файла

Более новые версии SQLite используют размер базы данных в заголовке, если он доступен, но возвращаются к фактическому размеру файла, если размер базы данных в заголовке недействителен

Размер базы данных в заголовке считается действительным только в том случае, если он ненулевой и если 4-байтовый счётчик изменений по смещению 24 точно совпадает с 4-байтовым номером version-valid-for по смещению 92. Размер базы данных в заголовке всегда действителен, когда база данных изменяется только с использованием последних версий SQLite — версий 3.7.0 (2010-07-21) и более поздних

Если устаревшая версия SQLite выполняет запись в базу данных, она не будет знать о необходимости обновить размер базы данных в заголовке, и поэтому размер базы данных в заголовке может оказаться некорректным. Но устаревшие версии SQLite также оставят номер version-valid-for по смещению 92 без изменений, поэтому он не будет совпадать со счётчиком изменений

Следовательно, недействительные размеры базы данных в заголовке можно обнаружить (и проигнорировать), наблюдая за несовпадением счётчика изменений с номером version-valid-for

Список свободных страниц

Неиспользуемые страницы в файле базы данных хранятся в свободном списке (freelist). 4-байтовое целое число в формате big-endian по смещению 32 хранит номер страницы первой страницы свободного списка или ноль, если свободный список пуст. 4-байтовое целое число в формате big-endian по смещению 36 хранит общее количество страниц в свободном списке

Куки схемы

Куки схемы (schema cookie) — это 4-байтовое целое число в формате big-endian по смещению 40, которое увеличивается каждый раз при изменении схемы базы данных. Подготовленный оператор компилируется для конкретной версии схемы базы данных. При изменении схемы базы данных оператор должен быть подготовлен заново

При выполнении подготовленного оператора он сначала проверяет куки схемы, чтобы убедиться, что значение совпадает с тем, которое было при подготовке оператора; если куки схемы изменилось, оператор либо автоматически перекомпилируется и выполняется повторно, либо завершается с ошибкой SQLITE_SCHEMA

Номер формата схемы

Номер формата схемы — это 4-байтовое целое число в формате big-endian по смещению 44. Номер формата схемы аналогичен номерам версий формата файла для чтения и записи по смещениям 18 и 19, за исключением того, что номер формата схемы относится к высокоуровневому форматированию SQL, а не к низкоуровневому форматированию b-дерева. В настоящее время определены четыре номера формата схемы:

• Формат 1 поддерживается всеми версиями SQLite начиная с версии 3.0.0 (2004-06-18).
• Формат 2 добавляет возможность строкам в одной таблице иметь различное количество столбцов для поддержки функциональности ALTER TABLE ... ADD COLUMN. Поддержка чтения и записи формата 2 была добавлена в SQLite версии 3.1.3 от 2005-02-20.
• Формат 3 добавляет возможность дополнительным столбцам, добавленным с помощью ALTER TABLE ... ADD COLUMN, иметь ненулевые значения по умолчанию. Эта возможность была добавлена в SQLite версии 3.1.4 от 2005-03-11.
• Формат 4 заставляет SQLite учитывать ключевое слово DESC в объявлениях индексов. (Ключевое слово DESC игнорируется в индексах для форматов 1, 2 и 3.) Формат 4 также добавляет два новых булевых значения типа записи (serial types 8 и 9). Поддержка формата 4 была добавлена в SQLite 3.3.0 от 2006-01-10.

Новые файлы баз данных, создаваемые SQLite, по умолчанию используют формат 4. Параметр SQLITE_DBCONFIG_LEGACY_FILE_FORMAT для C-языкового интерфейса sqlite3_db_config() можно использовать для того, чтобы SQLite создавал новые файлы баз данных с использованием формата 1. Номер версии формата можно сделать равным 1 по умолчанию вместо 4, установив SQLITE_DEFAULT_FILE_FORMAT=1 во время компиляции

Если база данных полностью пуста, если у неё нет схемы, то номер формата схемы может быть равен нулю

Рекомендуемый размер кэша

4-байтовое знаковое целое число в формате big-endian по смещению 48 — это рекомендуемый размер кэша в страницах для файла базы данных. Это значение является лишь рекомендацией, и SQLite не обязан её соблюдать. В качестве рекомендуемого размера используется абсолютное значение целого числа. Рекомендуемый размер кэша можно задать с помощью прагмы default_cache_size

Настройки инкрементального вакуума

Два 4-байтовых целых числа в формате big-endian по смещениям 52 и 64 используются для управления режимами auto_vacuum и incremental_vacuum. Если целое число по смещению 52 равно нулю, то страницы карты указателей (ptrmap) отсутствуют в файле базы данных и ни auto_vacuum, ни incremental_vacuum не поддерживаются

Если целое число по смещению 52 ненулевое, то оно является номером страницы наибольшей корневой страницы в файле базы данных, файл базы данных будет содержать страницы ptrmap, и режим должен быть либо auto_vacuum, либо incremental_vacuum. В последнем случае целое число по смещению 64 равно true для incremental_vacuum и false для auto_vacuum

Если целое число по смещению 52 равно нулю, то целое число по смещению 64 также должно быть равно нулю

Кодировка текста

4-байтовое целое число в формате big-endian по смещению 56 определяет кодировку, используемую для всех текстовых строк, хранящихся в базе данных. Значение 1 означает UTF-8. Значение 2 означает UTF-16le. Значение 3 означает UTF-16be. Никакие другие значения не допускаются

Заголовочный файл sqlite3.h определяет макросы препроцессора C: SQLITE_UTF8 как 1, SQLITE_UTF16LE как 2 и SQLITE_UTF16BE как 3 — для использования вместо числовых кодов кодировки текста

Номер пользовательской версии

4-байтовое целое число в формате big-endian по смещению 60 — это пользовательская версия, которая устанавливается и запрашивается с помощью прагмы user_version. Пользовательская версия не используется SQLite

Идентификатор приложения

4-байтовое целое число в формате big-endian по смещению 68 — это «идентификатор приложения» (Application ID), который может быть задан командой PRAGMA application_id для идентификации базы данных как принадлежащей конкретному приложению или связанной с ним. Идентификатор приложения предназначен для файлов баз данных, используемых в качестве формата файлов приложения

Идентификатор приложения может использоваться такими утилитами, как file(1), для определения конкретного типа файла, а не просто для вывода сообщения «SQLite3 Database». Список назначенных идентификаторов приложений можно найти в файле magic.txt в репозитории исходного кода SQLite

Номер версии библиотеки записи и номер version-valid-for

4-байтовое целое число в формате big-endian по смещению 96 хранит значение SQLITE_VERSION_NUMBER для библиотеки SQLite, которая последней изменяла файл базы данных. 4-байтовое целое число в формате big-endian по смещению 92 — это значение счётчика изменений на момент сохранения номера версии. Целое число по смещению 92 указывает, для какой транзакции действителен номер версии, и иногда называется «номером version-valid-for»

Пространство заголовка, зарезервированное для расширения

Все остальные байты заголовка файла базы данных зарезервированы для будущего расширения и должны быть установлены в ноль

Страница байтов блокировки

Страница байтов блокировки — это единственная страница файла базы данных, содержащая байты со смещениями от 1073741824 до 1073742335 включительно. Файл базы данных размером не более 1073741824 байт не содержит страницы байтов блокировки. Файл базы данных размером более 1073741824 байт содержит ровно одну страницу байтов блокировки

Страница байтов блокировки зарезервирована для использования специфичной для операционной системы реализацией VFS при реализации примитивов блокировки файла базы данных. SQLite не использует страницу байтов блокировки

Ядро SQLite никогда не читает и не записывает страницу байтов блокировки, хотя специфичные для операционной системы реализации VFS могут по своему усмотрению читать или записывать байты на странице байтов блокировки в соответствии с потребностями и особенностями базовой системы

Реализации VFS для unix и win32, встроенные в SQLite, не выполняют запись на страницу байтов блокировки, однако сторонние реализации VFS для других операционных систем могут это делать

Страница байтов блокировки появилась из-за необходимости поддержки Win95, которая была преобладающей операционной системой на момент разработки данного формата файла и поддерживала только обязательную блокировку файлов. Все современные операционные системы, о которых нам известно, поддерживают рекомендательную блокировку файлов, поэтому страница байтов блокировки больше не является действительно необходимой, однако сохраняется для обратной совместимости

Список свободных страниц

Файл базы данных может содержать одну или несколько страниц, которые не используются активно. Неиспользуемые страницы могут появляться, например, при удалении информации из базы данных. Неиспользуемые страницы хранятся в списке свободных страниц и повторно используются при необходимости выделения дополнительных страниц

Список свободных страниц организован в виде связного списка магистральных страниц списка свободных страниц, каждая из которых содержит номера страниц для нуля или более листовых страниц списка свободных страниц

Магистральная страница списка свободных страниц состоит из массива 4-байтовых целых чисел в формате big-endian. Размер массива равен максимальному количеству целых чисел, умещающихся в используемом пространстве страницы. Минимальное используемое пространство составляет 480 байт, поэтому массив всегда содержит не менее 120 элементов

Первое целое число на магистральной странице списка свободных страниц — это номер следующей магистральной страницы списка свободных страниц в списке, или ноль, если это последняя магистральная страница. Второе целое число на магистральной странице списка свободных страниц — это количество следующих далее указателей на листовые страницы

Обозначим второе целое число на магистральной странице списка свободных страниц как L. Если L больше нуля, то целые числа с индексами массива от 2 до L+1 включительно содержат номера листовых страниц списка свободных страниц

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

Ошибка в версиях SQLite до 3.6.0 (2008-07-16) приводила к тому, что база данных сообщалась как повреждённая, если любой из последних 6 элементов массива магистральной страницы списка свободных страниц содержал ненулевые значения. В более новых версиях SQLite эта проблема отсутствует

Однако более новые версии SQLite по-прежнему избегают использования последних шести элементов массива магистральной страницы списка свободных страниц, чтобы файлы баз данных, созданные более новыми версиями SQLite, могли читаться более старыми версиями SQLite

Количество страниц в списке свободных страниц хранится как 4-байтовое целое число в формате big-endian в заголовке базы данных со смещением 36 от начала файла. Заголовок базы данных также хранит номер первой магистральной страницы списка свободных страниц как 4-байтовое целое число в формате big-endian со смещением 32 от начала файла

Страницы B-дерева

Алгоритм b-дерева обеспечивает хранение пар ключ/данные с уникальными и упорядоченными ключами на устройствах хранения, ориентированных на страницы. Для получения справочной информации о b-деревьях см. Knuth, The Art Of Computer Programming, том 3 «Sorting and Searching», страницы 471–479. SQLite использует два варианта b-деревьев

«Табличные b-деревья» используют 64-битный знаковый целочисленный ключ и хранят все данные в листьях. «Индексные b-деревья» используют произвольные ключи и не хранят никаких данных вообще

Страница b-дерева является либо внутренней страницей, либо листовой страницей. Листовая страница содержит ключи, а в случае табличного b-дерева каждый ключ имеет связанные данные. Внутренняя страница содержит K ключей вместе с K+1 указателями на дочерние страницы b-дерева. «Указатель» на внутренней странице b-дерева — это просто 32-битный беззнаковый целочисленный номер дочерней страницы

Количество ключей на внутренней странице b-дерева, K, почти всегда не менее 2 и обычно значительно больше 2. Единственное исключение — когда страница 1 является внутренней страницей b-дерева

Страница 1 имеет на 100 байт меньше доступного пространства для хранения из-за наличия заголовка базы данных в начале этой страницы, и поэтому иногда (редко), если страница 1 является внутренней страницей b-дерева, она может содержать только один ключ. Во всех остальных случаях K равно 2 или более. Верхняя граница K — максимальное количество ключей, умещающихся на странице

Большие ключи в индексных b-деревьях разбиваются на страницы переполнения таким образом, чтобы ни один отдельный ключ не использовал более одной четверти доступного пространства хранения на странице, и поэтому каждая внутренняя страница способна хранить не менее 4 ключей

Целочисленные ключи табличных b-деревьев никогда не бывают достаточно большими, чтобы требовать переполнения, поэтому переполнение ключей происходит только в индексных b-деревьях

Определим глубину листового b-дерева как 1, а глубину любого внутреннего b-дерева — как на единицу больше максимальной глубины любого из его дочерних элементов. В правильно сформированной базе данных все дочерние элементы внутреннего b-дерева имеют одинаковую глубину

На внутренней странице b-дерева указатели и ключи логически чередуются, причём указатели находятся на обоих концах. Все ключи на одной странице уникальны и логически упорядочены по возрастанию слева направо. Для любого ключа X указатели слева от X ссылаются на страницы b-дерева, на которых все ключи меньше или равны X. Указатели справа от X ссылаются на страницы, где все ключи больше X

На внутренней странице b-дерева каждый ключ и указатель непосредственно слева от него объединяются в структуру, называемую «ячейкой». Крайний правый указатель хранится отдельно. Листовая страница b-дерева не имеет указателей, но по-прежнему использует структуру ячеек для хранения ключей в индексных b-деревьях или ключей и содержимого в табличных b-деревьях. Данные также содержатся в ячейке

Каждая страница b-дерева имеет не более одной родительской страницы b-дерева. Страница b-дерева без родителя называется корневой страницей. Корневая страница b-дерева вместе с замыканием её дочерних элементов образует полное b-дерево. Возможно (и на самом деле довольно распространено) наличие полного b-дерева, состоящего из одной страницы, которая является одновременно листом и корнем

Поскольку существуют указатели от родителей к дочерним элементам, каждую страницу полного b-дерева можно найти, зная только корневую страницу. Следовательно, b-деревья идентифицируются по номеру их корневой страницы

Страница b-дерева является либо страницей табличного b-дерева, либо страницей индексного b-дерева. Все страницы в каждом полном b-дереве имеют одинаковый тип: либо табличный, либо индексный. В файле базы данных существует одно табличное b-дерево для каждой таблицы rowid в схеме базы данных, включая системные таблицы, такие как sqlite_schema

В файле базы данных существует одно индексное b-дерево для каждого индекса в схеме, включая неявные индексы, созданные ограничениями уникальности. С виртуальными таблицами не связано ни одного b-дерева. Конкретные реализации виртуальных таблиц могут использовать теневые таблицы для хранения данных, но эти теневые таблицы будут иметь отдельные записи в схеме базы данных

Таблицы WITHOUT ROWID используют индексные b-деревья вместо табличных b-деревьев, поэтому в файле базы данных существует одно индексное b-дерево для каждой таблицы WITHOUT ROWID. B-дерево, соответствующее таблице sqlite_schema, всегда является табличным b-деревом и всегда имеет корневую страницу 1. Таблица sqlite_schema содержит номер корневой страницы для каждой другой таблицы и индекса в файле базы данных

Каждая запись в табличном b-дереве состоит из 64-битного знакового целочисленного ключа и до 2147483647 байт произвольных данных. (Ключ табличного b-дерева соответствует rowid SQL-таблицы, которую реализует b-дерево.) Внутренние страницы табличных b-деревьев хранят только ключи и указатели на дочерние элементы. Все данные содержатся в листьях табличного b-дерева

Каждая запись в индексном b-дереве состоит из произвольного ключа длиной до 2147483647 байт и не содержит данных

Определим «полезную нагрузку» ячейки как секцию ячейки произвольной длины. Для индексного b-дерева ключ всегда имеет произвольную длину, и поэтому полезная нагрузка — это ключ. В ячейках внутренних страниц табличного b-дерева нет элементов произвольной длины, и поэтому эти ячейки не имеют полезной нагрузки. Листовые страницы табличного b-дерева содержат содержимое произвольной длины, и поэтому для ячеек на этих страницах полезная нагрузка — это содержимое

Когда размер полезной нагрузки ячейки превышает определённый порог (который будет определён позже), только первые несколько байт полезной нагрузки хранятся на странице b-дерева, а остаток хранится в связном списке страниц переполнения содержимого

Страница b-дерева разделена на области в следующем порядке:

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

100-байтовый заголовок файла базы данных находится только на странице 1, которая всегда является страницей табличного b-дерева. Все остальные страницы b-дерева в файле базы данных не содержат этот 100-байтовый заголовок

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

Заголовок страницы b-дерева имеет размер 8 байт для листовых страниц и 12 байт для внутренних страниц. Все многобайтовые значения в заголовке страницы представлены в формате big-endian. Заголовок страницы b-дерева состоит из следующих полей:

• Значение 2 (0x02) означает, что страница является внутренней страницей индексного b-дерева.
• Значение 5 (0x05) означает, что страница является внутренней страницей табличного b-дерева.
• Значение 10 (0x0a) означает, что страница является листовой страницей индексного b-дерева.
• Значение 13 (0x0d) означает, что страница является листовой страницей табличного b-дерева.

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

Содержимое ячеек хранится в области содержимого ячеек страницы b-дерева. SQLite стремится размещать ячейки как можно ближе к концу страницы b-дерева, чтобы оставить место для будущего роста массива указателей на ячейки. Область между последним элементом массива указателей на ячейки и началом первой ячейки является нераспределённой областью

Если страница не содержит ячеек (что возможно только для корневой страницы таблицы, не содержащей строк), то смещение до области содержимого ячеек будет равно размеру страницы минус байты зарезервированного пространства

Если база данных использует размер страницы 65536 байт и зарезервированное пространство равно нулю (обычное значение для зарезервированного пространства), то смещение содержимого ячеек пустой страницы должно быть 65536. Однако это целое число слишком велико для хранения в 2-байтовом беззнаковом целом числе, поэтому вместо него используется значение 0

Свободный блок — это структура, используемая для идентификации нераспределённого пространства внутри страницы b-дерева. Свободные блоки организованы в цепочку. Первые 2 байта свободного блока — это целое число в формате big-endian, представляющее смещение в странице b-дерева до следующего свободного блока в цепочке, или ноль, если свободный блок является последним в цепочке

Третий и четвёртый байты каждого свободного блока образуют целое число в формате big-endian, представляющее размер свободного блока в байтах, включая 4-байтовый заголовок. Свободные блоки всегда соединены в порядке возрастания смещений. Второе поле заголовка страницы b-дерева — это смещение первого свободного блока, или ноль, если на странице нет свободных блоков

В правильно сформированной странице b-дерева перед первым свободным блоком всегда будет находиться не менее одной ячейки

Свободный блок требует не менее 4 байт пространства. Если в области содержимого ячеек существует изолированная группа из 1, 2 или 3 неиспользуемых байт, эти байты составляют фрагмент. Общее количество байт во всех фрагментах хранится в пятом поле заголовка страницы b-дерева. В правильно сформированной странице b-дерева общее количество байт во фрагментах не может превышать 60

Общий объём свободного пространства на странице b-дерева состоит из размера нераспределённой области плюс суммарный размер всех свободных блоков плюс количество фрагментированных свободных байт

SQLite может время от времени реорганизовывать страницу b-дерева таким образом, чтобы не было свободных блоков или фрагментированных байт, все неиспользуемые байты содержались в области нераспределённого пространства, а все ячейки были плотно упакованы в конце страницы. Это называется «дефрагментацией» страницы b-дерева

Целое число переменной длины, или «varint», — это статическое кодирование Хаффмана для 64-битных целых чисел в дополнительном коде, которое использует меньше места для малых положительных значений. Varint имеет длину от 1 до 9 байт

Varint состоит либо из нуля или более байт с установленным старшим битом, за которыми следует один байт с незаданным старшим битом, либо из девяти байт — в зависимости от того, что короче. Младшие семь битов каждого из первых восьми байт и все 8 битов девятого байта используются для восстановления 64-битного целого числа в дополнительном коде

Varint представлены в формате big-endian: биты, взятые из более раннего байта varint, более значимы, чем биты из более поздних байт

Формат ячейки зависит от того, на какой странице b-дерева она находится. Ниже показаны элементы ячейки в порядке их появления для различных типов страниц b-дерева

Листовая ячейка табличного b-дерева (заголовок 0x0d):

• Varint, представляющий общее количество байт полезной нагрузки, включая любое переполнение
• Varint, представляющий целочисленный ключ, он же «rowid»
• Начальная часть полезной нагрузки, которая не переходит на страницы переполнения
• 4-байтовый целочисленный номер страницы в формате big-endian для первой страницы списка страниц переполнения — опускается, если вся полезная нагрузка умещается на странице b-дерева

Внутренняя ячейка табличного b-дерева (заголовок 0x05):

• 4-байтовый номер страницы в формате big-endian, являющийся указателем на левый дочерний элемент
• Varint, представляющий целочисленный ключ

Листовая ячейка индексного b-дерева (заголовок 0x0a):

• Varint, представляющий общее количество байт ключевой полезной нагрузки, включая любое переполнение
• Начальная часть полезной нагрузки, которая не переходит на страницы переполнения
• 4-байтовый целочисленный номер страницы в формате big-endian для первой страницы списка страниц переполнения — опускается, если вся полезная нагрузка умещается на странице b-дерева

Внутренняя ячейка индексного b-дерева (заголовок 0x02):

• 4-байтовый номер страницы в формате big-endian, являющийся указателем на левый дочерний элемент
• Varint, представляющий общее количество байт ключевой полезной нагрузки, включая любое переполнение
• Начальная часть полезной нагрузки, которая не переходит на страницы переполнения
• 4-байтовый целочисленный номер страницы в формате big-endian для первой страницы списка страниц переполнения — опускается, если вся полезная нагрузка умещается на странице b-дерева

Объём полезной нагрузки, переходящей на страницы переполнения, также зависит от типа страницы. Для следующих вычислений пусть U — используемый размер страницы базы данных, то есть общий размер страницы минус зарезервированное пространство в конце каждой страницы. И пусть P — размер полезной нагрузки

В следующем тексте символ X представляет максимальный объём полезной нагрузки, который может быть сохранён непосредственно на странице b-дерева без перехода на страницу переполнения, а символ M представляет минимальный объём полезной нагрузки, который должен быть сохранён на странице b-дерева до того, как допускается переполнение

Листовая ячейка табличного b-дерева: пусть X равно U-35. Если размер полезной нагрузки P меньше или равен X, то вся полезная нагрузка хранится на листовой странице b-дерева. Пусть M равно ((U-12)*32/255)-23, а K равно M+((P-M)%(U-4)). Если P больше X, то количество байт, хранящихся на листовой странице табличного b-дерева, равно K, если K меньше или равно X, или M в противном случае. Количество байт, хранящихся на листовой странице, никогда не бывает меньше M

Внутренние страницы табличных b-деревьев не имеют полезной нагрузки, и поэтому никогда не бывает полезной нагрузки для переполнения

Листовая или внутренняя ячейка индексного b-дерева: пусть X равно ((U-12)64/255)-23. Если размер полезной нагрузки P меньше или равен X, то вся полезная нагрузка хранится на странице b-дерева. Пусть M равно ((U-12)32/255)-23, а K равно M+((P-M)%(U-4)). Если P больше X, то количество байт, хранящихся на странице индексного b-дерева, равно K, если K меньше или равно X, или M в противном случае. Количество байт, хранящихся на странице индекса, никогда не бывает меньше M

Ниже приведено альтернативное описание того же вычисления:

• X равно U-35 для листовых страниц табличного b-дерева или ((U-12)*64/255)-23 для страниц индекса.
• M всегда равно ((U-12)*32/255)-23.
• Пусть K равно M+((P-M)%(U-4)).
• Если P<=X, то все P байт полезной нагрузки хранятся непосредственно на странице b-дерева без переполнения.
• Если P>X и K<=X, то первые K байт из P хранятся на странице b-дерева, а оставшиеся P-K байт хранятся на страницах переполнения.
• Если P>X и K>X, то первые M байт из P хранятся на странице b-дерева, а оставшиеся P-M байт хранятся на страницах переполнения.

Пороги переполнения разработаны таким образом, чтобы обеспечить минимальный коэффициент ветвления 4 для индексных b-деревьев и гарантировать, что достаточная часть полезной нагрузки находится на странице b-дерева, чтобы заголовок записи обычно был доступен без обращения к странице переполнения. Оглядываясь назад, разработчик логики b-дерева SQLite осознал, что эти пороги могли бы быть значительно проще

Однако вычисления не могут быть изменены без получения несовместимого формата файла. И текущие вычисления работают хорошо, пусть они и несколько сложны

Страницы переполнения полезной нагрузки ячейки

Когда полезная нагрузка ячейки b-дерева слишком велика для страницы b-дерева, излишек переносится на страницы переполнения. Страницы переполнения образуют связный список. Первые четыре байта каждой страницы переполнения — это целое число в формате big-endian, представляющее номер следующей страницы в цепочке, или ноль для последней страницы в цепочке. С пятого байта до последнего используемого байта хранится содержимое переполнения

Страницы карты указателей (Ptrmap)

Страницы карты указателей (ptrmap) — это дополнительные страницы, вставляемые в базу данных для повышения эффективности работы режимов auto_vacuum и incremental_vacuum. Другие типы страниц в базе данных, как правило, содержат указатели от родительских страниц к дочерним

Например, внутренняя страница b-дерева содержит указатели на дочерние страницы b-дерева, а цепочка переполнения содержит указатель от более ранних звеньев к более поздним. Страница ptrmap содержит информацию о связях в обратном направлении — от дочерней страницы к родительской

Страницы ptrmap должны присутствовать в любом файле базы данных, в котором значение наибольшей корневой страницы b-дерева по смещению 52 в заголовке базы данных не равно нулю. Если значение наибольшей корневой страницы b-дерева равно нулю, база данных не должна содержать страниц ptrmap

В базе данных со страницами ptrmap первая такая страница находится на странице 2. Страница ptrmap состоит из массива записей по 5 байт каждая. Пусть J — количество 5-байтовых записей, умещающихся в используемом пространстве страницы. (Иными словами, J=U/5.) Первая страница ptrmap будет содержать информацию об обратных указателях для страниц с 3 по J+2 включительно

Вторая страница карты указателей будет находиться на странице J+3 и предоставлять информацию об обратных указателях для страниц с J+4 по 2*J+3 включительно. И так далее для всего файла базы данных

В базе данных, использующей страницы ptrmap, все страницы в позициях, определяемых вычислением из предыдущего абзаца, должны быть страницами ptrmap, и никакая другая страница не может являться страницей ptrmap. Исключение: если страница byte-lock оказывается на том же номере страницы, что и страница ptrmap, то в этом единственном случае ptrmap смещается на следующую страницу

Каждая 5-байтовая запись на странице ptrmap предоставляет информацию об обратной ссылке для одной из страниц, непосредственно следующих за картой указателей. Если страница B является страницей ptrmap, то информация об обратной ссылке для страницы B+1 предоставляется первой записью карты указателей. Информация о странице B+2 предоставляется второй записью. И так далее

Каждая 5-байтовая запись ptrmap состоит из одного байта информации о «типе страницы», за которым следует 4-байтовый номер страницы в формате big-endian. Распознаются пять типов страниц:

• Корневая страница b-дерева. Номер страницы должен быть равен нулю.
• Страница списка свободных страниц. Номер страницы должен быть равен нулю.
• Первая страница цепочки переполнения полезной нагрузки ячейки. Номер страницы — это страница b-дерева, содержащая ячейку, содержимое которой переполнилось.
• Страница в цепочке переполнения, не являющаяся первой. Номер страницы — это предыдущая страница цепочки переполнения.
• Некорневая страница b-дерева. Номер страницы — это родительская страница b-дерева.

В любом файле базы данных, содержащем страницы ptrmap, все корневые страницы b-дерева должны располагаться раньше любых некорневых страниц b-дерева, страниц переполнения полезной нагрузки ячеек или страниц списка свободных страниц. Это ограничение гарантирует, что корневая страница никогда не будет перемещена в ходе операции auto-vacuum или incremental-vacuum

Логика auto-vacuum не умеет обновлять поле root_page таблицы sqlite_schema, поэтому необходимо предотвращать перемещение корневых страниц во время auto-vacuum для сохранения целостности таблицы sqlite_schema. Корневые страницы перемещаются в начало файла базы данных операциями CREATE TABLE, CREATE INDEX, DROP TABLE и DROP INDEX

Уровень схемы: как SQL-конструкции отображаются на файл

Приведённый выше текст описывает низкоуровневое устройство формата файла SQLite. Механизм b-дерева предоставляет мощное и эффективное средство доступа к большому набору данных. В этом разделе описывается, как низкоуровневый слой b-дерева используется для реализации высокоуровневых возможностей SQL

Формат записи

Данные листовой страницы b-дерева таблицы и ключ страницы b-дерева индекса были охарактеризованы выше как произвольная последовательность байтов. В предыдущем обсуждении упоминалось, что один ключ может быть меньше другого, однако не было определено, что означает «меньше». В текущем разделе эти упущения будут устранены

Полезная нагрузка — будь то данные b-дерева таблицы или ключи b-дерева индекса — всегда представлена в «формате записи». Формат записи определяет последовательность значений, соответствующих столбцам таблицы или индекса. Формат записи задаёт количество столбцов, тип данных каждого столбца и содержимое каждого столбца

Формат записи активно использует представление 64-битных знаковых целых чисел в виде целых чисел переменной длины (varint), определённое выше

Запись содержит заголовок и тело, именно в таком порядке. Заголовок начинается с одного varint, определяющего общее количество байтов в заголовке. Значение varint — это размер заголовка в байтах, включая сам varint размера. За varint размера следуют один или несколько дополнительных varint, по одному на каждый столбец. Эти дополнительные varint называются числами «серийного типа» (serial type) и определяют тип данных каждого столбца

Varint размера заголовка и varint серийных типов обычно состоят из одного байта. Varint серийных типов для больших строк и BLOB-объектов могут занимать два или три байта, однако это исключение, а не правило. Формат varint очень эффективен для кодирования заголовка записи

Значения каждого столбца в записи следуют непосредственно за заголовком. Для серийных типов 0, 8, 9, 12 и 13 значение занимает ноль байтов. Если все столбцы относятся к этим типам, то секция тела записи пуста

Запись может содержать меньше значений, чем количество столбцов в соответствующей таблице. Это может произойти, например, после того, как SQL-оператор ALTER TABLE ... ADD COLUMN увеличил количество столбцов в схеме таблицы, не изменив уже существующие строки таблицы. Отсутствующие значения в конце записи заполняются значением по умолчанию для соответствующих столбцов, определённым в схеме таблицы

Порядок сортировки записей

Порядок ключей в индексном b-дереве определяется порядком сортировки записей, которые эти ключи представляют. Сравнение записей происходит столбец за столбцом. Столбцы записи просматриваются слева направо. Первая пара столбцов, значения которых не равны, определяет относительный порядок двух записей. Порядок сортировки отдельных столбцов следующий:

• Значения NULL (серийный тип 0) сортируются первыми.
• Числовые значения (серийные типы с 1 по 9) сортируются после NULL в числовом порядке.
• Текстовые значения (нечётные серийные типы 13 и выше) сортируются после числовых значений в порядке, определяемом функцией сравнения (collating function) столбца.
• Значения BLOB (чётные серийные типы 12 и выше) сортируются последними в порядке, определяемом функцией memcmp().

Для вычисления порядка текстовых полей необходима функция сравнения для каждого столбца. SQLite определяет три встроенные функции сравнения:

• BINARY — сравнивает строки побайтово с помощью функции memcmp() из стандартной библиотеки C.
• NOCASE — аналогична BINARY, за исключением того, что символы ASCII в верхнем регистре (от 'A' до 'Z') приводятся к нижнему регистру перед выполнением сравнения. Приведение к нижнему регистру выполняется только для символов ASCII. NOCASE не реализует универсальное сравнение Unicode без учёта регистра.
• RTRIM — аналогична BINARY, за исключением того, что лишние пробелы в конце любой из строк не влияют на результат. Иными словами, строки будут считаться равными, если они отличаются только количеством пробелов в конце.

Дополнительные специфичные для приложения функции сравнения можно добавить в SQLite с помощью интерфейса sqlite3_create_collation()

Функция сравнения по умолчанию для всех строк — BINARY. Альтернативные функции сравнения для столбцов таблицы можно указать в операторе CREATE TABLE с помощью предложения COLLATE в определении столбца. При индексировании столбца для него в индексе по умолчанию используется та же функция сравнения, что указана в операторе CREATE TABLE, однако это можно переопределить с помощью предложения COLLATE в операторе CREATE INDEX

Представление таблиц SQL на диске

Каждая обычная таблица SQL в схеме базы данных представлена на диске в виде табличного b-дерева. Каждая запись в табличном b-дереве соответствует строке таблицы SQL. Rowid таблицы SQL является 64-битным знаковым целым числом — ключом для каждой записи в табличном b-дереве

Содержимое каждой строки таблицы SQL хранится в файле базы данных следующим образом: значения различных столбцов сначала объединяются в байтовый массив в формате записи, а затем этот байтовый массив сохраняется как полезная нагрузка (payload) в записи табличного b-дерева. Порядок значений в записи совпадает с порядком столбцов в определении таблицы SQL

Если таблица SQL включает столбец INTEGER PRIMARY KEY (который является псевдонимом rowid), то этот столбец присутствует в записи как значение NULL. SQLite всегда использует ключ табличного b-дерева, а не значение NULL, при обращении к столбцу INTEGER PRIMARY KEY

Если аффинность столбца равна REAL и этот столбец содержит значение, которое можно преобразовать в целое число без потери информации (если значение не имеет дробной части и не слишком велико для представления в виде целого числа), то столбец может быть сохранён в записи как целое число. SQLite преобразует значение обратно в число с плавающей точкой при извлечении его из записи

Таблицы WITHOUT ROWID и их представление

Если таблица SQL создана с использованием предложения WITHOUT ROWID в конце оператора CREATE TABLE, то такая таблица является таблицей WITHOUT ROWID и использует иное представление на диске. Таблица WITHOUT ROWID использует для хранения индексное b-дерево, а не табличное b-дерево

Ключом для каждой записи в b-дереве WITHOUT ROWID является запись, составленная из столбцов PRIMARY KEY, за которыми следуют все остальные столбцы таблицы. Столбцы первичного ключа располагаются в том порядке, в котором они были объявлены в предложении PRIMARY KEY, а остальные столбцы — в том порядке, в котором они встречаются в операторе CREATE TABLE

Таким образом, кодирование содержимого для таблицы WITHOUT ROWID аналогично кодированию содержимого для обычной таблицы с rowid, за исключением того, что порядок столбцов переставлен так, чтобы столбцы PRIMARY KEY шли первыми, а содержимое используется в качестве ключа в индексном b-дереве, а не в качестве данных в табличном b-дереве. Специальные правила кодирования для столбцов с аффинностью REAL применяются к таблицам WITHOUT ROWID так же, как и к таблицам с rowid

Подавление избыточных столбцов в PRIMARY KEY таблиц WITHOUT ROWID

Если PRIMARY KEY таблицы WITHOUT ROWID использует одни и те же столбцы с одинаковой последовательностью сравнения более одного раза, то второе и последующие вхождения этого столбца в определении PRIMARY KEY игнорируются. Например, следующие операторы CREATE TABLE задают одну и ту же таблицу, которая будет иметь абсолютно одинаковое представление на диске:

CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,c)) WITHOUT ROWID;
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,c,a,c)) WITHOUT ROWID;
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,A,a,C)) WITHOUT ROWID;

Типичные ошибки при работе с форматом файла SQLite

Понимание формата файла помогает избежать ряда практических ошибок. Я неоднократно наблюдал, как разработчики сталкиваются с одними и теми же проблемами при работе с файлами SQLite напрямую

Игнорирование горячих журналов при копировании файла. Если скопировать .db-файл без соответствующего журнала отката или WAL-файла, копия может оказаться в несогласованном состоянии. Правильный способ создания резервной копии — использовать API резервного копирования SQLite или команду .backup в sqlite3

Неверная интерпретация размера страницы 65536. Значение 0x00 0x01 по смещению 16 не означает страницу размером 1 байт — это специальное кодирование для 65536 байт. Код, который читает это поле как обычное big-endian целое число и не обрабатывает этот частный случай, будет работать некорректно

Прямое редактирование файла без обновления счётчика изменений. Если изменить содержимое файла базы данных в обход SQLite, счётчик изменений по смещению 24 не обновится. Другие процессы, кэшировавшие страницы, не узнают об изменениях и продолжат работать с устаревшими данными

Смешение версий SQLite при работе с форматом 4. Если база данных создана с форматом схемы 4 (по умолчанию в современных версиях SQLite), а затем открывается очень старой версией SQLite (до 3.3.0), индексы с ключевым словом DESC будут обрабатываться некорректно

Неучёт зарезервированного пространства при вычислении используемого размера страницы. Расширения, такие как SQLite Encryption Extension, используют байты в конце каждой страницы. Код, который вычисляет смещения внутри страницы без учёта зарезервированного пространства по смещению 20 заголовка, будет читать данные из неверных позиций

Ответы на эти вопросы могут быть для вас полезными

Почему SQLite хранит всю базу данных в одном файле?

Это архитектурное решение упрощает развёртывание и перенос данных: достаточно скопировать один файл. Всё состояние базы данных — страницы b-дерева, свободный список, схема — содержится в едином файловом пространстве, что исключает рассинхронизацию между несколькими файлами

Что произойдёт, если удалить журнал отката (rollback journal) или WAL-файл во время работы приложения?

Если журнал является «горячим» (то есть содержит данные незавершённой транзакции), его удаление приведёт к невозможности восстановления базы данных в согласованное состояние после сбоя. SQLite обнаружит отсутствие журнала при следующем открытии файла и не сможет выполнить восстановление, что может привести к повреждению данных

Как SQLite определяет, что файл базы данных принадлежит именно SQLite, а не другому формату?

Каждый допустимый файл SQLite начинается с магической строки «SQLite format 3» (16 байт, включая нулевой терминатор) по смещению 0. Утилиты вроде file(1) используют именно эту сигнатуру, а также идентификатор приложения (Application ID) по смещению 68, для определения типа файла

Зачем нужны страницы карты указателей (ptrmap), если b-дерево и так содержит указатели от родителей к дочерним страницам?

Страницы ptrmap хранят обратные указатели — от дочерних страниц к родительским. Они нужны исключительно для режимов auto_vacuum и incremental_vacuum: чтобы переместить страницу в конце файла на освободившееся место, SQLite должен знать, кто ссылается на эту страницу, и обновить соответствующий указатель. Без ptrmap это потребовало бы полного обхода всего b-дерева

Можно ли безопасно читать файл SQLite напрямую, минуя библиотеку?

Технически — да, если база данных не открыта другим процессом и нет горячего журнала. Однако необходимо корректно обрабатывать порядок байт (big-endian для всех многобайтовых полей), формат varint, зарезервированное пространство страниц и специальные случаи вроде кодирования размера страницы 65536. На практике использование официального C API SQLite или проверенных библиотек-обёрток значительно надёжнее прямого разбора файла