Какова минимальная занятость в B-деревьях?

Question

Я довольно новичок в концепции B-Tree, сейчас я читаю слайды для курса, который можно найти здесь: http://www-db.deis.unibo.it/courses/TBD/Lezioni/02%20-%20Indices.pdf

Я читал, что B-деревья имеют "минимальную загруженность" 50%.

Что это значит? Это хороший процент для минимальной вместимости? И лучше ли иметь большую / меньшую минимальную вместимость?

Спасибо

Answer 1

Этот ответ относится к ENGINE = InnoDB.

Для всех практических целей данный BTree является либо "полным", либо полным на 69%. Это не относится к отдельным блокам.

Отдельные блоки...

• При первоначальной загрузке BTree в ключевом порядке, он будет заполнен до 15/16.

• "Последний" блок может быть почти пустым - при условии, что вставка считает, что к дереву добавляется.

• При случайном заполнении будут разделяться блоки, которые оставят два последовательных блока заполненными примерно на 50% каждый.

• В долгосрочной перспективе (непрерывный отток и / или дополнения) к BTree, он достигает в среднем около 69%. (Это факт о BTrees.)

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

• Когда два соседних блока заполнены менее чем наполовину, код может попытаться объединить блоки.

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

Некоторые поставщики баз данных предоставляют всевозможные настройки для минимальной / максимальной / дополнительной загрузки. MySQL следует принципу KISS; ничего не настраивается. В результате BTrees достаточно эффективны. Кроме того, обратите внимание, что при индексировании существует ограниченный выбор (для InnoDB):

• PRIMARY KEY уникален и сгруппирован; здесь нет вариантов
• Вторичные индексы (если есть) не являются кластеризованными и имеют PRIMARY KEY столбец (ы) в листовом узле. То есть, чтобы найти всю строку с помощью вторичного ключа, есть два перехода по BTree.

Полезное правило (для блоков InnoDB по 16 КБ): около 100 элементов находятся в каждом узле BTree. Следствие: таблица триллионов строк или индекс будет иметь около 6 уровней в BTree. (Разве этот абзац не проще, чем эти формулы и т. Д. В вашей ссылке?)

InnoDB использует "деревья B+", поэтому последовательное сканирование может проходить от одного конечного узла к другому.

Смотрите также Википедию для другого обсуждения BTrees.

О, вернемся к вопросу о 50% - это "естественно". Подумайте о том, что делает "разбиение на блоки" (также называемое "разбиение на листы") - возьмите один полный блок и превратите его в два смежных полуобщих блока. Нет смысла просить что-либо кроме 50%. (Да, вы могли бы разделить полный блок на 3, но это кажется расточительным. Или вы могли бы разделить, прежде чем он полностью заполнится, но тогда ничего особенного не получится.)