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

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

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-дерева индекса
• Страница списка свободных страниц
  • Корневая страница списка свободных страниц
  • Листовая страница списка свободных страниц
• Страница переполнения полезной нагрузки
• Страница карты указателей
• Страница блокировочных байтов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3.9. Cookie схемы

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

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

Номер формата схемы — это 4-байтовое целое число с порядком байтов от старшего к младшему по смещению 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 в объявлениях индексов. (В индексах форматов 1, 2 и 3 ключевое слово DESC игнорируется.) Формат 4 также добавляет два новых логических значения типа записи (серийные типы 8 и 9). Поддержка формата 4 появилась в SQLite 3.3.0 от 2006-01-10.

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

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

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

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

1.3.12. Настройки инкрементной очистки

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

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

4-байтовое целое число с порядком байтов от старшего к младшему по смещению 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-байтовое целое число с порядком байтов от старшего к младшему по смещению 60 — это версия пользователя, которая задается и запрашивается с помощью прагмы user_version. SQLite не использует версию пользователя.

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

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

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

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

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

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

1.4. Страница блокировочных байтов

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

Страница блокировочных байтов зарезервирована для использования реализацией VFS, специфичной для операционной системы, при реализации примитивов блокировки файла базы данных. SQLite не использует страницу блокировочных байтов. Ядро SQLite никогда не читает и не записывает эту страницу, однако реализации VFS, специфичные для операционной системы, могут читать или записывать байты на странице блокировочных байтов в соответствии с особенностями и потребностями базовой системы. Встроенные в SQLite реализации VFS для Unix и Win32 не записывают данные на страницу блокировочных байтов, но сторонние реализации 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-деревьях см. в книге Кнута The Art Of Computer Programming, том 3, «Sorting and Searching», страницы 471–479. SQLite использует два варианта B-деревьев. «B-деревья таблиц» используют 64-битный целочисленный ключ со знаком и хранят все данные в листьях. «B-деревья индексов» используют ключи произвольного типа и не хранят данные.

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

Число ключей K на внутренней странице B-дерева почти всегда не меньше 2 и обычно значительно больше 2. Единственное исключение — случай, когда страница 1 является внутренней страницей B-дерева. На странице 1 доступно на 100 байт меньше места для хранения из-за заголовка базы данных в начале этой страницы, поэтому иногда (хотя и редко) внутренняя страница B-дерева на странице 1 может содержать только один ключ. Во всех остальных случаях 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-дерева разделена на области, расположенные в следующем порядке:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В любом файле базы данных, содержащем страницы ptrmap, все корневые страницы B-дерева должны располагаться перед любой некорневой страницей B-дерева, страницей переполнения полезной нагрузки ячейки или страницей списка свободных страниц. Это ограничение гарантирует, что корневая страница никогда не будет перемещена при выполнении auto-vacuum или incremental-vacuum. Логика auto-vacuum не умеет обновлять поле root_page таблицы sqlite_schema, поэтому для сохранения целостности таблицы sqlite_schema необходимо предотвращать перемещение корневых страниц при выполнении auto-vacuum. Корневые страницы перемещаются в начало файла базы данных операциями 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 очень эффективен для кодирования заголовка записи.

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

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

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

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

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

Для определения порядка текстовых полей необходима функция сортировки для каждого столбца. 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. При обращении к столбцу INTEGER PRIMARY KEY SQLite всегда использует ключ табличного B-дерева, а не значение NULL.

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

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

2.4.1. Исключение повторяющихся столбцов из 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;
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 и увеличивающееся на единицу для каждого ограничения, встреченного в определении таблицы. В таблице 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 SQL, таблица 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 автоматически удаляется при удалении таблицы. Если при обновлении таблицы AUTOINCREMENT соответствующая строка sqlite_sequence отсутствует, создаётся новая строка 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.idx. Столбец sqlite_stat1.tbl содержит имя таблицы, которой принадлежит индекс. В каждой такой строке поле sqlite_stat.stat содержит строку со списком целых чисел, за которым могут следовать ноль или более аргументов. Первое целое число в этом списке — приблизительное количество строк в индексе. (Количество строк в индексе совпадает с количеством строк в таблице, за исключением частичных индексов.) Второе целое число — приблизительное количество строк в индексе, имеющих одинаковое значение в первом столбце индекса. Третье целое число — количество строк в индексе, имеющих одинаковые значения в первых двух столбцах. N-е целое число (для N>1) — предполагаемое среднее количество строк в индексе, имеющих одинаковые значения в первых N-1 столбцах. Для индекса из K столбцов в столбце stat будет K+1 целых чисел. Если индекс уникален, последнее целое число будет равно 1.

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

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

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

Наличие токена "noskipscan" в поле sqlite_stat1.stat индекса запрещает использовать этот индекс с оптимизацией skip-scan.

В будущих усовершенствованиях SQLite в конец столбца stat могут добавляться новые текстовые токены. Для обеспечения совместимости нераспознанные токены в конце столбца 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 до 3.6.18 или после 3.7.8 не читает и не записывает таблицу sqlite_stat2. Таблица 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 до 3.7.9 не читает и не записывает таблицу sqlite_stat3. Если используется параметр компиляции 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 до 3.8.1 не читает и не записывает таблицу sqlite_stat4. Таблица 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 соответственно.

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

Заголовок журнала отката дополняется нулями до размера одного сектора (определяемого целочисленным значением размера сектора по смещению 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». Когда база данных работает в режиме WAL, все подключения к этой базе данных должны использовать WAL. Для конкретной базы данных используется либо журнал отката, либо WAL, но не оба одновременно. WAL всегда находится в том же каталоге, что и файл базы данных, и имеет то же имя, что и файл базы данных, с добавленной строкой "-wal".

4.1. Формат файла WAL

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

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

Заголовок WAL имеет размер 32 байта и состоит из следующих восьми беззнаковых 32-разрядных целых чисел в порядке от старшего байта к младшему:

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

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

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

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

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

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

Алгоритм вычисления контрольной суммы работает только с данными, длина которых кратна 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». В начале первой новой транзакции записи значение salt-1 в заголовке WAL увеличивается, а значение salt-2 рандомизируется. Эти изменения значений salt делают недействительными старые кадры в WAL, для которых уже была создана контрольная точка, но которые ещё не были перезаписаны, и не позволяют создавать для них контрольные точки повторно.

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

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

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

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

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

4.6. Формат wal-index

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

Назначение wal-index — быстро отвечать на следующий вопрос:

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

Значение M из предыдущего абзаца — это значение «mxFrame», определённое в разделе 4.5. Оно считывается в начале транзакции и задаёт максимальный кадр из WAL, который будет использовать читатель.

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

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

Последнее обновление этой страницы: 2025-12-25 10:33:36Z