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

В данном документе описывается и определяется формат файла базы данных на диске, используемый всеми выпусками SQLite с версии 3.0.0 (18.06.2004).

1. Файл базы данных

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

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

1.1. Журналы с данными

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

1.2. Страницы

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

Страницы пронумерованы, начиная с 1. Максимальный номер страницы — 4294967294 (2³² - 2). Минимальный размер базы данных SQLite — одна страница размером 512 байт. Максимальный размер базы данных составил бы 4294967294 страницы по 65536 байт на страницу или 281 474 976 579 584 байт (примерно 281 терабайт). Обычно SQLite достигнет максимального размера файла, установленного файловой системой или аппаратным обеспечением диска, задолго до достижения собственного внутреннего лимита.

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

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

• Страница B-дерева
  • Внутренняя страница B-дерева таблицы
  • Листовая страница B-дерева таблицы
  • Внутренняя страница B-дерева индекса
  • Листовая страница B-дерева индекса
• Страница freelist
  • Страница ствола freelist
  • Листовая страница freelist
• Страница переполнения полезной нагрузки
• Страница карты указателей
• Страница байта блокировки

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

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

Первые 100 байтов файла базы данных составляют заголовок файла базы данных. Заголовок файла базы данных разделён на поля, как показано в таблице ниже. Все многобайтовые поля в заголовке файла базы данных хранятся с байтом старшего порядка первым (big-endian).

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

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

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

Двухбайтовое значение, начинающееся с смещения 16, определяет размер страницы базы данных. Для версий SQLite 3.7.0.1 (2010-08-04) и более ранних эта величина интерпретируется как целое число в формате big-endian и должна быть степенью двойки от 512 до 32768 включительно. Начиная с версии SQLite 3.7.1 (2010-08-23), поддерживается размер страницы 65536 байт. Значение 65536 не помещается в двухбайтовое целое число, поэтому для указания размера страницы 65536 байт значение в смещении 16 равно 0x00 0x01. Это значение можно интерпретировать как 1 в формате big-endian и рассматривать как магическое число для представления размера страницы 65536. Или можно рассматривать двухбайтовое поле как число в формате little-endian и сказать, что оно представляет собой размер страницы, деленный на 256. Эти два способа интерпретации поля размера страницы эквивалентны.

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

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

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

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

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

1.3.5. Дробные части полезной нагрузки

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

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

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

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

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

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

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

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

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

1.3.9. Хеш схемы

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

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

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

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

Новые файлы баз данных, созданные SQLite, по умолчанию используют формат 4. Pragma legacy_file_format может быть использован для создания новых файлов базы данных с использованием формата 1. Номер версии формата можно сделать по умолчанию равным 1 вместо 4, установив SQLITE_DEFAULT_FILE_FORMAT=1 во время компиляции.

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

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

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

1.3.12. Настройки инкрементного вакуума

Два 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 также должно быть равно нулю.

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

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, для использования вместо числовых кодов кодировки текста.

1.3.14. Номер версии пользователя

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

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

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

1.3.16. Номер версии библиотеки записи и номер версии, действительный для

В 4-байтовом целом числе со знаком большого эндиана по смещению 96 хранится значение SQLITE_VERSION_NUMBER для библиотеки SQLite, которая последней изменяла файл базы данных. 4-байтовое целое число со знаком большого эндиана по смещению 92 содержит значение счётчика изменений (change counter) в момент сохранения номера версии. Целое число по смещению 92 указывает, к какой транзакции относится номер версии, и иногда называется «номером версии-действительным-для».

1.3.17. Зарезервированное место в заголовке для расширения

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

1.4. Страница с байтом блокировки

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

Страница с байтом блокировки предназначена для использования реализацией VFS (VFS), специфичной для операционной системы, для реализации примитивов блокировки файла базы данных. SQLite не использует страницу с байтом блокировки. Ядро SQLite никогда не читает и не записывает страницу с байтом блокировки, хотя реализации VFS, специфичные для операционной системы, могут выбрать чтение или запись байтов на странице с байтом блокировки в соответствии с потребностями и особенностями подлежащей системы. Реализации VFS для unix и win32, которые включены в SQLite, не записывают на страницу с байтом блокировки, но сторонние реализации VFS для других операционных систем могут.

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

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

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

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

Страница-ствол списка свободных страниц состоит из массива целых чисел со знаком большого эндиана по 4 байта. Размер массива равен количеству целых чисел, которые помещаются в используемое пространство страницы. Минимальное используемое пространство составляет 480 байт, поэтому массив всегда имеет длину не менее 120 элементов. Первое целое число на странице-стволе списка свободных страниц — номер страницы следующей страницы-ствола списка свободных страниц в списке или ноль, если это последняя страница-ствол списка свободных страниц. Второе целое число на странице-стволе списка свободных страниц — количество указателей на страницы-листья списка свободных страниц, которые следуют за ним. Назовём второе целое число на странице-стволе списка свободных страниц L. Если L больше нуля, то целые числа с индексами массива от 2 до L+1 включительно содержат номера страниц страниц-листьев списка свободных страниц.

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

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

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

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

Алгоритм B-дерева обеспечивает хранение ключей/данных с уникальными и упорядоченными ключами на страницах ориентированных устройствах хранения. Для получения справочной информации о B-деревьях, см. Кнута, «Искусство программирования, том 3», «Сортировка и поиск», страницы 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-дерево таблиц для каждой таблицы строк в схеме базы данных, включая системные таблицы, такие как 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-дерева делится на области в следующем порядке:

1. 100-байтовый заголовок файла базы данных (находится только на странице 1)
2. 8 или 12-байтовый заголовок страницы B-дерева
3. Массив указателей ячеек
4. Незанятое пространство
5. Область содержимого ячеек
6. Зарезервированная область

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

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

Заголовок страницы B-дерева имеет размер 8 байт для страниц-листьев и 12 байт для внутренних страниц. Все многобайтовые значения в заголовке страницы — большого эндиана. Заголовок страницы 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»
• Начальная часть полезной нагрузки, которая не переходит на страницы переполнения.
• Четырёхбайтовое целое число big-endian, номер страницы первой страницы списка страниц переполнения — пропускается, если вся полезная нагрузка помещается на странице b-дерева.

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

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

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

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

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

• Четырёхбайтовое целое число big-endian, которое является указателем на левое поддерево.
• Varint, представляющий общее количество байтов полезной нагрузки ключа, включая любые переполнения
• Начальная часть полезной нагрузки, которая не переходит на страницы переполнения.
• Четырёхбайтовое целое число 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-деревьев не имеют полезной нагрузки, поэтому никогда не возникает необходимости переполнения.

Листовая или внутренняя ячейка индексного 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 понял, что эти пороговые значения можно сделать намного проще. Однако вычисления нельзя изменить без изменения несовместимого формата файла. И текущие вычисления работают хорошо, даже если они немного сложны.

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

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

1.8. Страницы карты указателей или страниц ptrmap

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

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

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

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

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

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

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

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

2. Уровень схемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4. Представление таблиц без 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.

2.4.1. Исключение избыточных столбцов в первичном ключе таблиц WITHOUT ROWID

Если первичный ключ таблицы WITHOUT ROWID использует одни и те же столбцы с одной и той же последовательностью сортировки более одного раза, то второй и последующие случаи указания этого столбца в определении первичного ключа игнорируются. Например, следующие операторы 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;
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,a,a,a,c)) WITHOUT ROWID;

Первый пример, конечно, является предпочтительным определением таблицы. Все примеры создают таблицу WITHOUT ROWID с двумя столбцами PRIMARY KEY, «a» и «c», в этом порядке, за которыми следуют два столбца данных «b» и «d», также в этом порядке.

2.5. Представление индексов SQL

Каждый индекс SQL, явным образом объявленный с помощью оператора CREATE INDEX или подразумеваемый ограничением UNIQUE или PRIMARY KEY, соответствует индексного b-дереву в файле базы данных. Каждая запись в индексном b-дереве соответствует одной строке в связанной таблице SQL. Ключом индексного b-дерева является запись, составленная из индексируемых столбцов, за которыми следует ключ соответствующей строки таблицы. Для обычных таблиц ключом строки является rowid, а для таблиц WITHOUT ROWID ключом строки является PRIMARY KEY. Поскольку каждая строка в таблице имеет уникальный ключ строки, все ключи в индексе уникальны.

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

2.5.1. Исключение избыточных столбцов в вторичных индексах WITHOUT ROWID

В индексе таблицы WITHOUT ROWID, если столбец PRIMARY KEY также является столбцом в индексе и имеет соответствующую последовательность сортировки, то индексируемый столбец не повторяется в суффиксе ключа таблицы в конце записи индекса. Рассмотрим следующий SQL:

CREATE TABLE ex25(a,b,c,d,e,PRIMARY KEY(d,c,a)) WITHOUT rowid;
CREATE INDEX ex25ce ON ex25(c,e);
CREATE INDEX ex25acde ON ex25(a,c,d,e);
CREATE INDEX ex25ae ON ex25(a COLLATE nocase,e);

Каждая строка в индексе ex25ce представляет собой запись со следующими столбцами: c, e, d, a. Первые два столбца — это индексируемые столбцы c и e. Остальные столбцы — это первичный ключ соответствующей строки таблицы. Обычно первичным ключом были бы столбцы d, c и a, но поскольку столбец c уже указан ранее в индексе, он исключается из суффикса ключа.

В крайнем случае, когда индексируемые столбцы охватывают все столбцы PRIMARY KEY, индекс будет состоять только из индексируемых столбцов. Пример ex25acde выше демонстрирует это. Каждая запись в индексе ex25acde состоит только из столбцов a, c, d и e в указанном порядке.

Каждая строка в ex25ae содержит пять столбцов: a, e, d, c, a. Столбец «a» повторяется, поскольку первая встреча с «a» имеет функцию сортировки «nocase», а вторая — «binary». Если столбец «a» не повторяется, а таблица содержит две или более записи с одинаковым значением «e», и где «a» отличается только регистром, то все эти записи таблицы будут соответствовать одной записи в индексе, что нарушит взаимно однозначное соответствие между таблицей и индексом.

Исключение избыточных столбцов в суффиксе ключа записи индекса происходит только в таблицах WITHOUT ROWID. В обычной таблице rowid запись индекса всегда заканчивается rowid, даже если столбец INTEGER PRIMARY KEY является одним из индексируемых столбцов.

2.6. Хранение схемы базы данных SQL

Страница 1 файла базы данных — это корневая страница табличного b-дерева, содержащего специальную таблицу под названием «sqlite_schema». Это b-дерево известно как «таблица схемы», поскольку оно хранит полную схему базы данных. Структура таблицы sqlite_schema такая, как если бы она была создана с помощью следующего SQL:

CREATE TABLE sqlite_schema(
  type text,
  name text,
  tbl_name text,
  rootpage integer,
  sql text
);

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

Столбец sqlite_schema.type будет содержать один из следующих текстовых строк: 'table', 'index', 'view' или 'trigger' в зависимости от типа определённого объекта. Строка 'table' используется как для обычных, так и для виртуальных таблиц.

Столбец sqlite_schema.name будет содержать имя объекта. Ограничения UNIQUE и PRIMARY KEY на таблицах заставляют SQLite создавать внутренние индексы с именами в формате «sqlite_autoindex_TABLE_N», где TABLE заменяется именем таблицы, содержащей ограничение, а N — целое число, начинающееся с 1 и увеличивающееся на 1 с каждым встреченным ограничением в определении таблицы. В таблице WITHOUT ROWID нет записи в sqlite_schema для PRIMARY KEY, но имя «sqlite_autoindex_TABLE_N» резервируется для PRIMARY KEY так, как если бы запись sqlite_schema существовала. Это повлияет на нумерацию последующих ограничений UNIQUE. Имя «sqlite_autoindex_TABLE_N» никогда не выделяется для INTEGER PRIMARY KEY, ни в таблицах rowid, ни в таблицах WITHOUT ROWID.

Столбец sqlite_schema.tbl_name содержит имя таблицы или представления, с которыми связан объект. Для таблицы или представления столбец tbl_name является копией столбца name. Для индекса tbl_name — это имя таблицы, которая индексируется. Для триггера столбец tbl_name хранит имя таблицы или представления, которое вызывает срабатывание триггера.

Столбец sqlite_schema.rootpage хранит номер страницы корневого b-дерева для таблиц и индексов. Для строк, определяющих представления, триггеры и виртуальные таблицы, столбец rootpage равен 0 или NULL.

Столбец sqlite_schema.sql хранит текстовый SQL, описывающий объект. Этот SQL-текст — это оператор CREATE TABLE, CREATE VIRTUAL TABLE, CREATE INDEX, CREATE VIEW или CREATE TRIGGER, который, если он будет выполнен в файле базы данных, когда он является основной базой данных подключения соединения базы данных, воссоздаст объект. Текст обычно является копией исходного оператора, используемого для создания объекта, но с применёнными нормализациями, чтобы текст соответствовал следующим правилам:

• Ключевые слова CREATE, TABLE, VIEW, TRIGGER и INDEX в начале оператора преобразуются в прописные буквы.
• Ключевое слово TEMP или TEMPORARY удаляется, если оно встречается после начального ключевого слова CREATE.
• Любой квалификатор имени базы данных, который встречается перед именем создаваемого объекта, удаляется.
• Удаляются ведущие пробелы.
• Все пробелы, следующие за первыми двумя ключевыми словами, преобразуются в один пробел.

Текст в столбце sqlite_schema.sql является копией исходного текста оператора CREATE, который создал объект, за исключением нормализации, как описано выше, и изменений, внесённых последующими операторами ALTER TABLE. sqlite_schema.sql имеет значение NULL для внутренних индексов, которые автоматически создаются ограничениями UNIQUE или PRIMARY KEY.

2.6.1. Альтернативные названия таблицы схемы

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

1. sqlite_master
2. sqlite_temp_schema
3. sqlite_temp_master

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

2.6.2. Внутренние схемные объекты

В дополнение к таблицам, индексам, представлениям и триггерам, созданным приложением и/или разработчиком с помощью операторов CREATE, таблица sqlite_schema может содержать ноль или более записей для внутренних схемных объектов, которые создаются SQLite для собственного внутреннего использования. Имена внутренних схемных объектов всегда начинаются с «sqlite_», и любая таблица, индекс, представление или триггер, имя которых начинается с «sqlite_», является внутренним схемным объектом. SQLite запрещает приложениям создавать объекты, имена которых начинаются с «sqlite_».

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

• Индексы с именами в формате «sqlite_autoindex_TABLE_N», которые используются для реализации ограничений UNIQUE и PRIMARY KEY на обычных таблицах.

• Таблица с именем «sqlite_sequence», которая используется для отслеживания максимального исторического INTEGER PRIMARY KEY для таблицы, использующей AUTOINCREMENT.

• Таблицы с именами в формате «sqlite_statN», где N — целое число. Такие таблицы хранят статистику базы данных, собранную командой ANALYZE и используемую планировщиком запросов для определения наилучшего алгоритма для каждого запроса.

Новые имена внутренних схемных объектов, всегда начинающиеся с «sqlite_», могут быть добавлены в формат файла SQLite в будущих версиях.

2.6.3. Таблица sqlite_sequence

Таблица sqlite_sequence — это внутренняя таблица, используемая для реализации AUTOINCREMENT. Таблица sqlite_sequence создаётся автоматически при создании любой обычной таблицы с целочисленным первичным ключом AUTOINCREMENT. После создания таблица sqlite_sequence существует в таблице sqlite_schema навсегда; её нельзя удалить. Структура таблицы sqlite_sequence:

CREATE TABLE sqlite_sequence(name,seq);

В таблице sqlite_sequence есть одна строка для каждой обычной таблицы, использующей AUTOINCREMENT. Имя таблицы (как оно отображается в sqlite_schema.name) находится в поле sqlite_sequence.name, а наибольшее значение INTEGER PRIMARY KEY, когда-либо вставленное в эту таблицу, находится в поле sqlite_sequence.seq. Новые автоматически сгенерированные целочисленные первичные ключи для таблиц AUTOINCREMENT гарантированно будут больше, чем значение sqlite_sequence.seq для этой таблицы. Если поле sqlite_sequence.seq таблицы AUTOINCREMENT уже имеет максимальное целочисленное значение (9223372036854775807), то попытки добавления новых строк в эту таблицу с автоматически сгенерированным целочисленным первичным ключом приведут к ошибке SQLITE_FULL. Поле sqlite_sequence.seq автоматически обновляется при необходимости при вставке новых записей в таблицу AUTOINCREMENT. Строка sqlite_sequence для таблицы AUTOINCREMENT автоматически удаляется при удалении таблицы. Если строка sqlite_sequence для таблицы AUTOINCREMENT отсутствует при обновлении таблицы AUTOINCREMENT, то создаётся новая строка sqlite_sequence. Если значение sqlite_sequence.seq для таблицы AUTOINCREMENT вручную установлено на значение, отличное от целого числа, и впоследствии происходит попытка вставки или обновления таблицы AUTOINCREMENT, то поведение не определено.

Код приложения может изменять таблицу sqlite_sequence, добавляя новые строки, удаляя строки или изменяя существующие строки. Однако код приложения не может создать таблицу sqlite_sequence, если она не существует. Код приложения может удалить все записи из таблицы sqlite_sequence, но код приложения не может удалить таблицу sqlite_sequence.

2.6.4. Таблица sqlite_stat1

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

CREATE TABLE sqlite_stat1(tbl,idx,stat);

Обычно в таблице sqlite_stat1 по одной строке на каждый индекс, где индекс идентифицируется именем в столбце sqlite_stat1.idx. Столбец sqlite_stat1.tbl содержит имя таблицы, к которой принадлежит индекс. В каждой такой строке столбец sqlite_stat.stat будет строкой, состоящей из списка целых чисел, за которым следуют нулевые или более аргументов. Первое целое число в этом списке — приблизительное количество строк в индексе. (Количество строк в индексе равно количеству строк в таблице, за исключением частичных индексов). Второе целое число — приблизительное количество строк в индексе, у которых одинаковое значение в первом столбце индекса. Третье целое число — количество строк в индексе, у которых одинаковое значение для первых двух столбцов. N-е целое число (для N>1) — это оценочное среднее количество строк в индексе, у которых одинаковое значение для первых N-1 столбцов. Для индекса из K столбцов в столбце stat будет K+1 целое число. Если индекс уникальный, то последнее целое число будет равно 1.

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

Если присутствует аргумент «unordered», то планировщик запросов предполагает, что индекс неупорядочен и не будет использовать индекс для диапазонного запроса или для сортировки.

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

Наличие маркера «noskipscan» в поле sqlite_stat1.stat индекса предотвращает использование этого индекса с оптимизацией пропуска сканирования.

В будущем могут быть добавлены новые текстовые маркеры в конец столбца stat в будущих улучшениях SQLite. Для совместимости нераспознанные маркеры в конце столбца stat будут игнорироваться.

Если столбец sqlite_stat1.idx имеет значение NULL, то столбец sqlite_stat1.stat содержит одно целое число, которое является приблизительным количеством строк в таблице, идентифицированной sqlite_stat1.tbl. Если столбец sqlite_stat1.idx совпадает со столбцом sqlite_stat1.tbl, то таблица является таблицей WITHOUT ROWID, и поле sqlite_stat1.stat содержит информацию о дереве индекса b-дерева, которое реализует таблицу WITHOUT ROWID.

2.6.5. Таблица sqlite_stat2

Таблица sqlite_stat2 создаётся и используется только если SQLite скомпилирован с SQLITE_ENABLE_STAT2 и версия SQLite находится в диапазоне от 3.6.18 (2009-09-11) до 3.7.8 (2011-09-19). Таблица sqlite_stat2 не читается и не записывается никакой версией SQLite до 3.6.18 и после 3.7.8. Таблица sqlite_stat2 содержит дополнительную информацию о распределении ключей в индексе. Структура таблицы sqlite_stat2 следующая:

CREATE TABLE sqlite_stat2(tbl,idx,sampleno,sample);

Столбцы sqlite_stat2.idx и sqlite_stat2.tbl в каждой строке таблицы sqlite_stat2 идентифицируют индекс, описанный этой строкой. Обычно в таблице sqlite_stat2 содержится 10 строк для каждого индекса.

Записи sqlite_stat2 для индекса, у которых sqlite_stat2.sampleno находится в диапазоне от 0 до 9 включительно, являются выборками левого крайнего значения ключа в индексе, взятыми в равномерно распределённых точках по индексу. Пусть C — количество строк в индексе. Тогда выбираемые строки задаются формулой

rownumber = (i*C*2 + C)/20

Переменная i в предыдущем выражении изменяется от 0 до 9. Концептуально пространство индекса разделено на 10 равномерных ведер, и выборки представляют собой среднюю строку из каждого ведра.

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

2.6.6. Таблица sqlite_stat3

Таблица sqlite_stat3 используется только в том случае, если SQLite скомпилирован с SQLITE_ENABLE_STAT3 или SQLITE_ENABLE_STAT4 и если номер версии SQLite равен 3.7.9 (2011-11-01) или выше. Таблица sqlite_stat3 не читается и не записывается никакой версией SQLite до 3.7.9. Если используется опция компиляции SQLITE_ENABLE_STAT4 и номер версии SQLite равен 3.8.1 (2013-10-17) или выше, то sqlite_stat3 может быть прочитана, но не записана. Таблица sqlite_stat3 содержит дополнительную информацию о распределении ключей в индексе, информацию, которую планировщик запросов может использовать для разработки более эффективных и быстрых алгоритмов запросов. Структура таблицы sqlite_stat3 следующая:

CREATE TABLE sqlite_stat3(tbl,idx,nEq,nLt,nDLt,sample);

Обычно в таблице sqlite_stat3 несколько записей для каждого индекса. Столбец sqlite_stat3.sample содержит значение левого крайнего поля индекса, идентифицированного sqlite_stat3.idx и sqlite_stat3.tbl. Столбец sqlite_stat3.nEq содержит приблизительное число записей в индексе, у которых левое крайнее поле точно совпадает с выборкой. Столбец sqlite_stat3.nLt содержит приблизительное число записей в индексе, у которых левое крайнее поле меньше выборки. Столбец sqlite_stat3.nDLt содержит приблизительное число различных левых крайних записей в индексе, которые меньше выборки.

Может быть произвольное число записей sqlite_stat3 на индекс. Команда ANALYZE обычно генерирует таблицы sqlite_stat3, содержащие от 10 до 40 выборок, распределённых по ключевому пространству и с большими значениями nEq.

В правильно сформированной таблице sqlite_stat3 выборки для любого отдельного индекса должны появляться в том же порядке, в котором они встречаются в индексе. Другими словами, если запись с левым крайним столбцом S1 расположена раньше в дереве индекса b-дерева, чем запись с левым крайним столбцом S2, то в таблице sqlite_stat3 выборка S1 должна иметь меньший rowid, чем выборка S2.

2.6.7. Таблица sqlite_stat4

Таблица sqlite_stat4 создаётся и используется только если SQLite скомпилирован с SQLITE_ENABLE_STAT4 и если номер версии SQLite равен 3.8.1 (2013-10-17) или выше. Таблица sqlite_stat4 не читается и не записывается никакой версией SQLite до 3.8.1. Таблица sqlite_stat4 содержит дополнительную информацию о распределении ключей в индексе или о распределении ключей в первичном ключе таблицы WITHOUT ROWID. Планировщик запросов может иногда использовать дополнительную информацию в таблице sqlite_stat4 для разработки лучших и более быстрых алгоритмов запросов. Структура таблицы sqlite_stat4 следующая:

CREATE TABLE sqlite_stat4(tbl,idx,nEq,nLt,nDLt,sample);

В таблице sqlite_stat4 обычно содержится от 10 до 40 записей для каждого индекса, для которого доступны статистические данные, однако эти пределы не являются жёсткими границами. Значения столбцов в таблице sqlite_stat4 следующие:

sqlite_stat4 — это обобщение таблицы sqlite_stat3. Таблица sqlite_stat3 предоставляет информацию о левом столбце индекса, тогда как таблица sqlite_stat4 предоставляет информацию обо всех столбцах индекса.

Может быть произвольное количество записей sqlite_stat4 на индекс. Команда ANALYZE обычно генерирует таблицы sqlite_stat4, содержащие от 10 до 40 выборок, распределенных по ключевому пространству и с большими значениями nEq.

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

3. Журнал отката

Журнал отката — это файл, связанный с каждым файлом базы данных SQLite, который содержит информацию, используемую для восстановления файла базы данных в исходное состояние во время транзакции. Файл журнала отката всегда находится в той же директории, что и файл базы данных, и имеет то же имя, что и файл базы данных, но с добавленной строкой "-journal". С заданной базой данных может быть связан только один журнал отката, а значит, одновременно с одной базой данных может быть открыта только одна транзакция записи.

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

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

Журнал отката считается допустимым только в том случае, если он существует и содержит допустимый заголовок. Следовательно, транзакцию можно подтвердить тремя способами:

1. Файл журнала отката может быть удалён,
2. Файл журнала отката может быть усечён до нулевой длины, или
3. Заголовок файла журнала отката может быть перезаписан недействительным текстом заголовка (например, все нули).

Эти три способа подтверждения транзакции соответствуют настройкам DELETE, TRUNCATE и PERSIST соответственно, параметра journal_mode pragma.

Допустимый журнал отката начинается с заголовка в следующем формате:

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

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

Пусть размер страницы базы данных (значение целого числа в смещении 24 в заголовке журнала) равен N. Тогда формат записи страницы следующий:

Контрольная сумма — целое 32-битовое число без знака, вычисляемое следующим образом:

1. Инициализировать контрольную сумму значением контрольной суммы nonce, найденной в заголовке журнала в смещении 12.
2. Инициализировать индекс X как N-200 (где N — размер страницы базы данных в байтах).
3. Интерпретировать байт в смещении X в странице как 8-битовое целое число без знака и добавить значение этого целого числа к контрольной сумме.
4. Вычесть 200 из X.
5. Если X больше или равен нулю, вернуться к шагу 3.

Контрольная сумма используется для защиты от неполных записей записи страницы журнала после сбоя электропитания. Для минимизации риска того, что незаписанные сектора случайно содержат данные с той же страницы, которая была частью предыдущих журналов, каждый раз при запуске транзакции используется другой случайный nonce. Изменяя nonce для каждой транзакции, устаревшие данные на диске всё ещё будут генерировать неправильную контрольную сумму и будут обнаружены с высокой вероятностью. Контрольная сумма использует только выборочную выборку 32-битовых слов из записи данных по соображениям производительности — исследования дизайна во время планирования фаз SQLite 3.0.0 показали значительный спад производительности при вычислении контрольной суммы всей страницы.

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

Если M равно -1 в исходном заголовке журнала, то количество записей страниц, которые следуют, вычисляется путём подсчёта, сколько записей страниц поместится в доступном пространстве оставшейся части файла журнала.

4. Журнал предварительной записи

Начиная с версии 3.7.0 (2010-07-21), SQLite поддерживает новый механизм управления транзакциями, называемый «журналом предварительной записи» или «ЖПЗ». Когда база данных находится в режиме ЖПЗ, все подключения к этой базе данных должны использовать ЖПЗ. Определённая база данных будет использовать либо журнал отката, либо ЖПЗ, но не оба одновременно. ЖПЗ всегда находится в той же директории, что и файл базы данных, и имеет то же имя, что и файл базы данных, но с добавленной строкой "-wal".

4.1. Формат файла ЖПЗ

Файл ЖПЗ состоит из заголовка, за которым следуют ноль или более «кадров». Каждый кадр записывает изменённое содержимое одной страницы из файла базы данных. Все изменения в базе данных записываются путём записи кадров в ЖПЗ. Транзакции завершаются, когда записывается кадр, содержащий маркер подтверждения. Один ЖПЗ может и обычно записывает несколько транзакций. Периодически содержимое ЖПЗ переносится обратно в файл базы данных в операции, называемой «контрольной точкой».

Один файл ЖПЗ может быть повторно использован несколько раз. Другими словами, ЖПЗ может заполниться кадрами, а затем быть проверен, а затем новые кадры могут перезаписать старые. ЖПЗ всегда растёт от начала к концу. Контрольные суммы и счётчики, прикреплённые к каждому кадру, используются для определения, какие кадры в ЖПЗ являются допустимыми, а какие — остатками от предыдущих контрольных точек.

Заголовок ЖПЗ имеет размер 32 байта и состоит из восьми 32-битовых целых чисел без знака в формате big-endian:

Сразу после wal-заголовка находятся ноль или более кадров. Каждый кадр состоит из 24-байтового заголовка кадра, за которым следуют размер_страницы байт данных страницы. Заголовок кадра состоит из шести 32-битных беззнаковых целых чисел в формате big-endian, как показано ниже:

Кадр считается допустимым только в том случае, если выполняются следующие условия:

1. Значения соли-1 и соли-2 в заголовке кадра совпадают со значениями соли в заголовке wal

2. Значения контрольных сумм в последних 8 байтах заголовка кадра точно совпадают с вычисленной контрольной суммой последовательно по первым 24 байтам заголовка WAL и первым 8 байтам и содержимому всех кадров до и включая текущий кадр.

4.2. Алгоритм вычисления контрольной суммы

Контрольная сумма вычисляется путем интерпретации входных данных как четного числа беззнаковых 32-битных целых чисел: x(0) до x(N). 32-битные целые числа имеют порядок big-endian, если магическое число в первых 4 байтах заголовка WAL равно 0x377f0683, и имеют порядок little-endian, если магическое число равно 0x377f0682. Значения контрольных сумм всегда хранятся в заголовке кадра в формате big-endian, независимо от порядка байтов, используемого для вычисления контрольной суммы.

Алгоритм вычисления контрольной суммы работает только для содержимого, длина которого кратна 8 байтам. Другими словами, если входными данными являются x(0) до x(N), то N должно быть нечетным. Алгоритм вычисления контрольной суммы следующий:

 
s0 = s1 = 0
for i from 0 to n-1 step 2:
   s0 += x(i) + s1;
   s1 += x(i+1) + s0;
endfor
# result in s0 and s1

Выходные значения s0 и s1 являются взвешенными контрольными суммами с использованием фибоначчиевых весов в обратном порядке. (Наибольшее фибоначчиево взвешивание применяется к первому элементу суммируемой последовательности.) Значение s1 охватывает все 32-битные целочисленные члены последовательности, в то время как s0 пропускает последний член.

4.3. Алгоритм контрольной точки

При контрольной точке WAL сначала записывается в постоянное хранилище с использованием метода xSync для VFS. Затем валидное содержимое WAL перемещается в файл базы данных. Наконец, база данных записывается в постоянное хранилище с использованием другого вызова метода xSync. Операции xSync служат барьерами записи - все записи, запущенные до xSync, должны завершиться до начала записи, запущенной после xSync.

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

4.4. Сброс WAL

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

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

4.5. Алгоритм чтения

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

Для начала транзакции чтения читатель записывает количество кадров значений в WAL как "mxFrame". (Подробнее) Читатель использует это записанное значение mxFrame для всех последующих операций чтения. Новые транзакции могут быть добавлены в WAL, но до тех пор, пока читатель использует свое исходное значение mxFrame и игнорирует добавленное после содержимое, читатель будет видеть согласованную моментальную фотографию базы данных с одной точки во времени. Этот метод позволяет нескольким одновременным читателям просматривать разные версии содержимого базы данных одновременно.

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

4.6. Формат wal-индекса

По сути, wal-индекс является общей памятью, хотя текущие реализации VFS используют файл, отображенный в памяти, для обеспечения переносимости на уровне операционной системы. Файл, отображенный в памяти, находится в той же директории, что и база данных, и имеет то же имя, что и база данных, с добавленным суффиксом "-shm". Поскольку wal-индекс является общей памятью, SQLite не поддерживает journal_mode=WAL в сетевом файловом хранилище, когда клиенты находятся на разных машинах, так как все клиенты базы данных должны иметь возможность совместно использовать одну и ту же память.

Цель wal-индекса заключается в быстром ответе на этот вопрос:

Учитывая номер страницы P и максимальный индекс кадра WAL M, вернуть наибольший индекс кадра WAL для страницы P, который не превышает M, или вернуть NULL, если нет кадров для страницы P, которые не превышают M.

Значение M в предыдущем абзаце является значением "mxFrame", определенным в разделе 4.4, которое считывается в начале транзакции и которое определяет максимальный кадр из WAL, который будет использовать читатель.

Wal-индекс является временным. После сбоя wal-индекс восстанавливается из исходного файла WAL. VFS должен либо обрезать, либо обнулить заголовок wal-индекса при закрытии последнего подключения к нему. Поскольку wal-индекс является временным, он может использовать архитектурно-специфический формат; он не должен быть кроссплатформенным. Таким образом, в отличие от форматов базы данных и файла WAL, которые хранят все значения в формате big-endian, wal-индекс хранит многобайтовые значения в родном порядке байтов целевого компьютера.

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

Эта страница была последний раз изменена 14.11.2024 16:04:37 UTC