Как базы данных хранят значения ключей индекса (на диске) для полей переменной длины?

контекст

Этот вопрос относится к деталям реализации низкоуровневых индексов в системах баз данных SQL и NoSQL. Фактическая структура индекса (дерево B +, хэш, SSTable и т. Д.) Не имеет значения, поскольку этот вопрос конкретно относится к ключам, хранящимся в одном узле любой из этих реализаций.

Фон

В базах данных SQL (например, MySQL) и NoSQL (CouchDB, MongoDB и т. Д.), Когда вы строите индекс для столбца или поля данных JSON-документа, вы фактически заставляете базу данных создавать по существу отсортированный список всех эти значения вместе со смещением файла в основной файл данных, где находится запись, относящаяся к этому значению.

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

Простой классический пример SQL

Рассмотрим стандартную таблицу SQL, которая имеет простой 32-битный первичный ключ int, для которого мы создаем индекс, в результате мы получим на диске индекс целочисленных ключей, отсортированных и связанных с 64-битным смещением в файле данных, где запись живет, например:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

На диске представление ключей в индексе выглядит примерно так:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

Придерживаясь стандартных правил об оптимизации дискового ввода-вывода с файловыми системами и системами баз данных, скажем, вы храните ключи в блоках по 4 КБ на диске, что означает:

4096 bytes / 12 bytes per key = 341 keys per block

Игнорируя общую структуру индекса (дерево B +, хэш, отсортированный список и т. Д.), Мы одновременно читаем и записываем блоки по 341 ключу в память и при необходимости возвращаемся на диск.

Пример запроса

Используя информацию из предыдущего раздела, скажем, запрос приходит для «id = 2», классический поиск по БД происходит следующим образом:

1. Прочитать корень индекса (в данном случае 1 блок)
2. Бинарный поиск отсортированного блока, чтобы найти ключ
3. Получить смещение файла данных от значения
4. Найдите запись в файле данных, используя смещение
5. Вернуть данные звонящему

Настройка вопроса ...

Хорошо, вот где возникает вопрос ...

Шаг № 2 является наиболее важной частью, которая позволяет этим запросам выполняться за O (logn) время ... информация должна быть отсортирована, НО вы должны быть в состоянии быстро просмотреть список ... подробнее в частности, вы должны иметь возможность переходить к четко определенным смещениям по желанию для считывания значения ключа индекса в этой позиции.

После прочтения в блоке вы должны сразу же перейти на 170-ю позицию, прочитать значение ключа и посмотреть, является ли то, что вы ищете, GT или LT в этой позиции (и так далее, и так далее ...)

Единственный способ, которым вы могли бы перемещаться по данным в блоке, как это, был бы, если бы размеры значений ключа были все четко определены, как в нашем примере выше (4 байта, а затем 8 байтов на ключ).

ВОПРОС

Итак, вот где я застреваю с эффективным дизайном индекса ... для столбцов varchar в базах данных SQL или, более конкретно, для полей абсолютно свободной формы в базах документов, таких как CouchDB или NoSQL, где любое поле, которое вы хотите проиндексировать, может быть любым длина , как же реализовать ключевые ценности , которые находятся внутри блоков структуры индекса вы строите свои показатели из?

Например, предположим, что вы используете последовательный счетчик для идентификатора в CouchDB и индексируете твиты ... через несколько месяцев у вас будут значения от 1 до 100 000 000 000.

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

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

В какой-то момент это нарушается, и вам нужно переменное число байтов для хранения значения вашего ключа в индексах.

Суть еще более очевидна, если вы решите проиндексировать поле действительно переменной длины, например «tweet_message» или что-то в этом роде.

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

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

Это где я все споткнулся.

Поля со статическими типами в классических базах данных SQL (таких как bool, int, char и т. Д.), Я понимаю, индекс может просто заранее определить длину ключа и придерживаться его ... но в этом мире хранилищ данных документов я Озадачен тем, как они эффективно моделируют эти данные на диске, так что они все еще могут быть отсканированы за O (logn) время, и был бы признателен за любые разъяснения здесь.

Пожалуйста, дайте мне знать, если какие-либо разъяснения необходимы!

Обновление (ответ Грега)

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

Я рассмотрел 3 отдельные реализации СУБД (CouchDB, kivaloo и InnoDB), и все они решают эту проблему путем десериализации всего блока во внутренней структуре данных перед поиском значений в их среде выполнения (erlang / C).

Это то, что я считаю блестящим в предложении Грега; нормальный размер блока 2048 обычно имеет 50 или менее смещений, что приводит к очень маленькому блоку чисел, который необходимо будет прочитать.

Обновление (Потенциальные недостатки предложения Грега)

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

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

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

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

Обновление (Потенциальный потенциал)

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

Как только ключ, который вы ищете, найден, указатель может быть декодирован и отслежен.

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

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

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(ну, ключевые данные будут отсортированы в реальном примере, но вы поняли).

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