Как выложить данные B-Tree на диск?

Я знаю, как B-Tree работает в памяти, это достаточно просто реализовать. Тем не менее, в настоящее время я совершенно не понимаю, как найти макет данных, который эффективно работает на диске, чтобы:

  • Количество записей в B-дереве может расти бесконечно (или, по крайней мере, до> 1000 ГБ)
  • Операции копирования на уровне дисков сведены к минимуму
  • Значения могут иметь произвольный размер (т.е. без фиксированной схемы)

Если бы кто-нибудь мог дать представление о расположении структур B-Tree на уровне диска, я был бы очень благодарен. Особенно последний пункт пули вызывает у меня сильную головную боль. Я также был бы признателен за ссылки на книги, но большая часть литературы по базам данных, которую я видел, объясняет только высокоуровневую структуру (т. Е. "Так вы делаете это в памяти"), но пропускает мельчайшие подробности на макете диска.

Источник

2 ответа

Решение

Некоторая информация о внутренностях индекса оракула: http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

Заметки:

Базы данных напрямую не реализуют индексы, основанные на B-дереве, но на варианте, называемом B+ tree. Который согласно википедии:

Дерево B + можно рассматривать как дерево B, в котором каждый узел содержит только ключи (не пары ключ-значение) и к которому добавляется дополнительный уровень внизу со связанными листьями.

В целом, базы данных работают с блочно-ориентированным хранилищем, и b + tree более подходит для этого, чем b-tree.

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

Блок может быть или листом (содержит фактические данные) или ветвью (содержит указатели на узлы листа)

Игрушечная модель, как может быть реализована запись на диск (для блока размером 10 Кб для арифметического упрощения):

  1. на диске создан файл 10G (в нем 1000 блоков)
  2. первый блок назначается корневым, а следующий свободный - листом, а список конечных адресов - корневым.
  3. новые данные вставлены, текущий конечный узел заполняется значениями, пока не будет достигнут порог
  4. данные продолжают вставляться, следующие свободные выделяются как листовые блоки, и список листовых узлов обновляется
    1. после многих вставок текущему корневому узлу требуются дочерние элементы, поэтому следующий свободный блок выделяется как узел ветви, он копирует список из корневого узла, и теперь корень будет поддерживать только список промежуточных узлов.
    2. если требуется разделить блок узлов, следующий свободный блок выделяется как узел ветвления, добавляется в корневой список, а список конечных узлов разделяется между начальным и новым узлом ветвления.

Когда информация читается из большого индекса: может идти следующее:

  1. чтение первого / корневого блока (seek(0), read(10k)), который указывает на дочернего элемента, который находится в блоке 900
  2. читать блок 900 (поиск (900*10k), читать (10K)), который указывает на ребенка, который находится в блоке 5000
  3. читать блок 5000 (поиск (5000*10k), чтение (10K)), который указывает на конечный узел, расположенный в блоке 190
  4. читать блок 190 (искать (190*10k), читать (10K)) и извлекать из него интересующее значение

действительно большой индекс можно разделить на несколько файлов, тогда адрес блока будет выглядеть примерно так: (filename_id, address_relative_to_this_file)

Источник

Прочитайте это. Это, безусловно, поможет http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/

Источник
Другие вопросы по тегам