B-деревья — это стандартная реализация индексов в реляционных БД.
В ранее рассмотренных LSM-деревьях происходит только дописывание (и удаление устаревших) файлов, но не изменение существующих файлов. В отличие от них, B-деревья используют обновление на месте. Диск рассматривается как набор страниц заданного размера (обычно 4 КБ), допускающих перезапись. Все страницы имеют свой адрес/местоположение, благодаря чему одни страницы могут ссылаться на другие и собираться в дерево.
Поиск ключа начинается со страницы-корня. Она содержит несколько ключей и ссылок на дочерние страницы.
Например, мы ищем ключ 243. Переходим по ссылке на страницу диапазона 200—300. На этой странице вновь переходим по ссылке на страницу диапазона 230—250 и так добираемся до страницы, содержащей отдельные ключи. Это страница-лист. Она содержит или сами значения для ключей или ссылки на страницы, где можно найти эти значения.
Количество ссылок на дочерние страницы на одной странице B-дерева называется коэффициентом ветвления (branching factor). В примере на рисунке он равен 6, а практике обычно равен нескольким сотням.
Чтобы обновить значение ключа, нужно найти содержащую этот ключ страницу-лист, изменить там значение и записать ее обратно на диск (все ссылки на эту страницу останутся рабочими).
Чтобы добавить новый ключ, нужно найти страницу, в чей диапазон попадает новый ключ, и добавить его туда. Если на странице недостаточно места для него, то она разбивается на две полупустые страницы, а родительская страница обновляется, чтобы учесть это разбиение диапазона ключей на части.
Такой подход гарантирует, что дерево останется сбалансированным, то есть глубина B-дерева с n ключами будет равна
O(log n). Большинству БД хватает деревьев глубиной 3 или 4 уровня (четырехуровневое дерево страниц по 4 КБ с коэффициентом ветвления в 500 может хранить до 256 ТБ информации).В качестве усовершенствования страницы-листы могут ссылаться на страницы того же уровня слева и справа, чтобы просматривать ключи без возврата к родительским страницам.
Чтобы сделать БД отказоустойчивой используют специальный журнал упреждающей записи (write-ahead log — WAL, redo log). Это файл, в который все модификации B-деревьев записываются еще до того, как применяться к самим страницам дерева. Когда база возвращается в норму после сбоя, этот журнал используется для восстановления B-дерева в согласованное состояние.
#кабанчик #сисдиз