#24: Лучшая структура данных: B-tree, B+tree

[00:21] Здорово! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает то, как они работают, и делится знаниями со слушателями. В предыдущем выпуске мы познакомились с тем, как устроены диски и как мы с ними работаем, а также узнали внутреннее устройство слотированных страниц. Сегодня разберёмся с самой популярной структурой данных, которая используется в индексах, — это B-дерево. Поехали!

[01:04] Прежде чем погрузиться в мир структур данных, у меня для вас небольшая просьба. Кажется, что в этом подкасте мы рассматриваем довольно важные темы, которые хорошо бы знать всем разработчикам. Да чего уж там, и не только разработчикам. В то время как одни рассказывают нам, как правильно накрутить опыт в резюме, а другие обсуждают, почему это плохо, я стараюсь принести ценность в виде конкретных знаний. Так что поддержите подкаст лайком в Яндекс.Музыке или пятью звёздами в iTunes. Это поможет подкасту распространиться на площадках, и больше людей получит понимание современных баз данных, которое смогут применить в работе или при прохождении собеседования. Глядишь — и опыт накручивать не придётся. Ну а мы начинаем.

[01:50] B-дерево, или B-tree, было придумано ещё в далёком 1971 году. А уже к 1979-му образовалось целое семейство подобных структур данных. Чтобы плавно погрузиться в мир B-деревьев и понять, почему их так много и что их всех объединяет, давайте для начала рассмотрим более простую структуру данных — бинарное дерево поиска. Обычно бинарное дерево рисуют как кружочек с циферкой внутри, от которого вниз исходят две стрелочки к другим кружочкам. Внутри этих кружочков — тоже циферки, и из них так же исходит по две стрелочки к следующим кружочкам. Этот процесс можно повторять бесконечно. Самый верхний узел называется корнем, самые нижние — листьями, а всё, что посередине, — это просто узлы.

[02:40] Такая структура обладает инвариантом, который позволяет организовать эффективный поиск. Инвариант такой: все значения, которые находятся слева от текущего узла, строго меньше его значения, а все, что справа, — строго больше. То есть если в корне у нас пятёрка, то, пройдя по левому указателю, мы обнаружим число меньше 5, например 3. Пройдя снова влево от тройки, мы увидим число меньше тройки — двойку. А пройдя направо от тройки, найдём число больше 3 — это будет 4.

[03:12] Бинарный поиск по такой структуре выглядит очень просто. Мы стартуем от корня и смотрим, число, которое мы ищем, больше или меньше числа в корне. Если меньше — переходим по указателю в левый узел, если больше — в правый. Снова сверяем искомое число с числом в узле и принимаем решение, в какую сторону пойти дальше. И повторяем это действие до тех пор, пока не дойдём до узла, у которого указатель на следующий узел равен null, либо пока не найдём узел, значение которого равно тому, что мы ищем. Во втором случае — то есть когда мы нашли узел с нужным числом — результатом поиска будет положительный ответ: на вопрос «есть ли там число x?» мы отвечаем «да, есть». А вот когда мы оказались в ситуации, что переход по указателю невозможен, потому что указатель пустой, — мы отвечаем «нет», то есть в бинарном дереве нет числа x.

[04:07] Проблема этой структуры данных в том, что она может выродиться в односвязный список. Ну представьте: мы вставляем туда числа от 100 до 1. Сотка будет корнем, пройдя по указателю налево, увидим 99, ещё налево — 98, и так до самого конца. Где будет лежать единичка? Получается не дерево, а ветка какая-то. Поиск по этой ветке будет долгий, потому что мы потенциально перебираем все элементы. Другими словами, сложность поиска будет O(N), где N — число элементов в дереве, или в ветке в нашем случае.

[04:38] Эту проблему можно легко обойти, введя ещё один инвариант: дерево должно быть всегда сбалансировано. Сбалансированное дерево — это такое дерево, в котором для любого узла выполняется следующее условие: глубина левого поддерева должна отличаться от глубины правого поддерева не более чем на единицу. Другими словами, если мы возьмём дерево за корень пальчиками, так, как хватит, то оно, как сбалансированные весы, себя будет вести — его не перекосит ни в одну, ни в другую сторону. Это свойство даёт нам сложность поиска, которая равна O(log₂ N). Если у нас 1024 элемента в дереве, то мы сделаем максимум 10 переходов по указателю, чтобы найти искомый элемент. Что довольно неплохо.

[05:23] Однако баланс дерева сам себя не поддержит, и нам, как разработчикам структуры данных, нужно об этом позаботиться. Я не буду грузить сейчас про всякие левые или правые повороты, потому что это слишком сложно для подкаста. Что нам нужно понимать — так это то, что при любой вставке и при любом удалении мы должны проверять дерево на сбалансированность. И если мы из баланса вышли, то нужно просто переставить указатели так, чтобы баланс вернулся. Условно: мы на новогоднюю ёлку каждый раз вешаем игрушки с учётом того, чтобы они равномерно распределялись по ёлке. Если игрушку снимаем — не должны оставлять большую пустую дыру, а немножко переместить соседние игрушки, чтобы визуально ёлка была равномерно украшена.

[06:09] И это всё, конечно, хорошо, но в таком виде бинарные деревья на практике никто не использует, и никого они не интересуют. Мало кого устроит такой простой ответ на вопрос, есть ли в дереве число. Когда мы делаем поиск по структуре данных, мы, как правило, делаем это по ключу — хотим прочитать по ключу какое-то значение. Так вот, те циферки 5, 3, 4, которые я писал ранее, на самом деле это ключи, а рядом с ними лежат значения, которые нам нужны. В таком случае ответ бинарного поиска по ключу — не «да» или «нет», а целое значение, которое может представлять из себя что угодно, от циферки до картинки. Вопрос мы формулируем так: «дай мне значение по ключу x». Если получили null — такого ключа там нет; а если не null — вот оно, наше значение.

[06:57] Это уже похоже на то, что можно использовать на практике, только есть нюанс, и заключается он в том, что базы данных работают с дисками. А как мы понимаем из предыдущего выпуска, у дисков есть свои особенности. А именно: в HDD это очень медленное случайное чтение, а в SSD — постраничная организация операций чтения и записи. А если мы представим себе бинарное дерево, то оно на самом деле очень высокое: у него степень ветвления всего лишь 2, то есть мы можем пойти или направо, или налево. Таким образом, очень много указателей на следующие узлы, а много указателей — это потенциально много random seek’ов, тех самых случайных чтений, от которых мы хотим избавиться. Дерево высокое, оно производит много переходов по указателям, а на диске это делается медленно, и поэтому для работы с диском оно не подходит. Мало того, у классического бинарного дерева поиска, которое мы рассмотрели, ещё и локальность данных маленькая. Это можно частично решить с помощью другой структуры данных — там, страничное, по-моему, бинарное дерево, — но всё равно количество указателей и переходов по ним слишком большое для работы с дисками. Нам нужна такая структура данных, которая обеспечит высокую степень ветвления и низкую высоту.

[08:11] На практике B-деревья показывают себя гораздо эффективнее при работе с дисками, поэтому в большинстве случаев внутри индексов будет лежать именно B-дерево. Когда мы говорим про B-дерево, стоит отметить, что мы имеем в виду B+tree, а не классическое B-tree. Чтобы понять разницу, давайте представим себе библиотеку, в которой есть много стеллажей. Эти стеллажи делятся на группы, и на каждой группе написано: тут лежат книги, фамилии авторов которых начинаются на букву «А», «Б», тут — на «В», и так далее. Когда мы пытаемся найти книгу Пелевина, мы сразу же идём к группе стеллажей, на которой написано «П». Перейдя к этой группе, мы видим, что на каждом стеллаже сбоку написано «ПА» — то есть тут лежат книги только тех авторов, чьи фамилии начинаются на «ПА», как у меня, например, Пахомов, — а тут на «ПО». А вот то, что нам нужно, — «ПЕ». Смотрим на этот стеллаж и видим, что на каждой полке написано «ПЕВ», «ПЕВО» — как раз то, что нам нужно. Ну а полку просмотреть глазами недолго — и заветная книжка Пелевина найдена. То есть вместо того, чтобы стеллаж за стеллажом перебирать книги, мы используем индекс и за три шага доходим до полки с книгами Пелевина.

[09:24] Очень похожим образом устроена B+tree. Корень и внутренние узлы — это указатели на следующие узлы, по типу надписей на стеллажах. А листовые узлы — это узлы с данными, аналог полки с книгами из примера. Внутренний узел в B+tree устроен следующим образом. Скорее всего, это слотированная страница — мы рассматривали их в предыдущем выпуске. Страница содержит внутри себя, помимо заголовка, конечно, пары: они лежат один за одним — указатель, ключ, указатель, ключ, указатель, ключ и так далее, в отсортированном порядке. А если быть точнее, то список слотов хранит смещение так, что при последовательном переборе ключи будут отсортированы, а физически пары ключ-указатель могут лежать в произвольном порядке. Так устроен внутренний узел B+tree.

[10:15] Дальше. Допустим, мы перейдём по указателю для ключа 5 — тогда инвариант структуры данных гарантирует нам, что все ключи в следующем узле будут строго меньше, чем 5. Представим, что пятёрка — это самый левый ключ в узле, а рядом с ним лежит десятка. И вот если мы перейдём по указателю десятки, то окажемся в узле, где все значения меньше 10. Но так как у нас ещё есть узел с пятёркой, то мы можем сказать, что в узле под десяткой лежат ключи в диапазоне от 5 до 10. Что оказывается очень удобно. Ещё инвариант B+tree говорит нам, что самый правый указатель в узле указывает не на поддерево, где все ключи меньше, как везде, а наоборот — где все ключи больше, чем самое большое значение в текущем узле. Допустим, если у нас узел может хранить всего 3 ключа, то вот у нас лежат 5, 10, 15. По указателю 5 лежит всё, что меньше пятёрки. По указателю 10 — всё, что между пятёркой и десяткой. По указателю 15 — всё, что между десяткой и пятнадцаткой. А по так называемому правому указателю лежит всё, что больше 15. Так устроены внутренние узлы B+tree.

[11:24] А вот листовые узлы хранят в себе непосредственно данные — пары ключ-значение. И эти листовые узлы собой представляют, можно сказать, связанный список: когда мы до него дошли и поняли, что это листовой узел, просто начинаем перебирать один за одним по связанному списку ключи и значения, смотреть, это нужный нам ключ или нет. Штука состоит в том, что к этим нижним узлам можно не только прийти сверху, из корня B+tree, — мы можем ещё переместиться от левого листового узла к следующему, правому, и так далее по узлам. То есть, по сути, это связанный список связанных списков.

[12:03] Для чего это нужно? Для того, чтобы оптимизировать sequential scan, ну, или full scan, — то есть когда нам нужно перебрать все данные. Очень часто бывает так, что индекс не работает и нам так или иначе приходится сделать скан. Или, например, скан будет тупо быстрее, чем переход по индексу. И вот представьте: у вас такой связанный список из связанных списков. Один маленький список — это страница с данными; у него в конце лежит указатель на следующую страницу, в которой тоже связанный список; у той в конце — указатель на следующую, и так далее. Это вот все наши данные. И мы можем быстро их отсканировать при необходимости — потому что мы работаем с диском, а последовательное чтение быстрое. Но если нам нужно воспользоваться индексом, то над этим списком возвышается дерево из указателей на эти страницы, и мы можем быстренько, за логарифмическую сложность, прийти в нужную страницу. Так в целом устроены индексы B+tree.

[12:59] Если бы не было этих указателей между листовыми узлами, то sequential scan, конечно, тоже возможен, но как бы он выглядел тогда? Смотрите: мы дошли до самого левого нижнего узла, отсканировали его, прочитали весь. Что нам делать дальше? У нас нет указателя. Нам нужно пройти в родителя наверх, по родителю взять указатель на ближайший следующий узел и этот узел уже отсканировать. Потом опять прийти в родителя, перейти на следующий узел, опять отсканировать, потом прийти в родителя и понять, что родитель закончился, пойти в родителя родителя, и так далее. То есть этот sequential scan порождает очень много как раз тех самых random seek — мы начинаем прыгать по страницам. Вместо того чтобы просто одну плашку считать или попрыгать только между листовыми узлами, мы начинаем вверх-вниз, вверх-вниз, вверх-вниз. Такие вот американские горки, которые для работы с диском как раз плохо подходят, как мы знаем. Поэтому эти указатели внизу решают именно эту проблему.

[13:57] Также стоит отметить, что есть ещё один инвариант, который гарантирует нам, что абсолютно все страницы, или узлы, будут заполнены больше чем наполовину. То есть не существует таких узлов, у которых свободного места больше, чем половина, — потому что тогда это просто невыгодно. Тогда выгоднее взять то, что в этом узле, найти ещё один узел, в котором тоже меньше половины, и слить их в один, в котором будет больше половины. То есть у нас вместо двух страниц на диске оказывается одна, которая, да, почти заполнена, но зато она одна, и работать с ней просто эффективнее. Опять же, мы держим в голове, что нам нужно минимизировать количество случайных чтений и количество переходов по указателям, а наличие одной страницы вместо двух этому условию удовлетворяет. Поэтому дерево всегда заполнено — каждый его узел заполнен наполовину или более.

[14:50] Ну давайте представим себе вставку. Когда мы начинаем вставлять туда элемент и понимаем, что выходим за пределы, за возможности текущего узла, — он переполняется, и нам нужно его что сделать? Разделить на два. Разделение происходит в целом плюс-минус понятным образом: мы берём страницу, просто делим на две, меняем указатель в родительском узле — и вот у нас теперь две страницы. Но иногда это разделение, то есть порождение двух дополнительных страниц, может быть не так эффективно, как перелить часть данных из заполненного узла в соседний. То есть мы можем посмотреть в соседний узел на одном уровне дерева, увидеть, что у него есть место, — и устройство B+tree позволяет нам перелить туда часть данных. Опять же, немножко пошаманить с указателями в родителе — и таким образом новая страница не порождается, количество страниц в дереве остаётся тем же, просто мы немножко переставили указатели и поменяли данные. Это тоже возможно в B+tree. Такая вот удобная структура данных для работы с диском.

[15:52] Это при вставке. При удалении тоже есть момент, когда мы удаляем и понимаем, что вот сейчас в узле меньше половины заполненности, — тогда мы либо должны перелить данные из соседнего узла сюда, либо, наоборот, взять все данные из этого узла, перелить в соседний, а этот узел удалить. То есть удаление в этом плане не такое накладное, потому что удаление страницы — это не добавление ещё одной страницы. То есть мы себе проблему скорее уменьшаем, чем добавляем. Так в целом работает B+tree.

[16:24] Отличие его от B-tree, про которое я говорил в самом начале и которое вообще стоит в названии выпуска, в том, что B-tree может хранить value — эти вот значения — не только в листовых узлах. Они хранятся там же, прямо вместе со всеми ключами. То есть B-tree — это ближе к бинарному дереву поиска, которое хранит ключ и значение рядом. Но в чём проблема? Места хранится меньше, потому что меньше количество ключей в B-tree. Зато sequential scan, который так хорошо работает в B+tree, перестаёт работать эффективно в B-tree — потому что эти американские горки, прыжки по страницам, вверх-вниз, вверх-вниз, родитель-ребёнок, родитель-родителя и так далее, нужны, ведь там данные лежат, мы не можем их игнорировать. А в B+tree данных в дереве нет, они лежат внизу, и поэтому по нижнему списку мы можем просто легко пробежаться. Поэтому B+tree победила, и всегда, когда говорят о B-tree или какой-то его вариации, скорее всего, это будет что-то очень похожее на B+tree или прямо B+tree. Потому что они в итоге победили, их используют сейчас все, модифицируют поверх них, делают другие структуры данных. Поэтому если вы слышите «B-tree-индекс» — то это B+tree-индекс. Такие дела.

[17:41] Я понимаю, что в подкасте не всё может быть понятно, хотя я старался не перегружать деталями и рассказать вам суть. Но если вы хотите получше вникнуть в то, как работает B+tree, то в описании есть ссылка на интерактивную визуализацию. За пару минут вы точно поймёте, что к чему, и вопросов у вас не останется. Это просто обычная веб-морда, в которой можно выбрать, кстати, много структур данных, но я ставлю ссылку именно на B+tree. В общем, всё, что там нужно сделать, — это выбрать степень ветвления; для простоты понимания выберите 3 или 4, больше не надо. И там есть формочка, куда можно вставить данные и удалить их. Вот подаёте туда данные 1, 5, 3, 4, 7, 8, 10 — посмотрите, как ведёт себя эта структура, как разделяются узлы, создаются новые, перетекают ключи. Потом поудаляете данные — посмотрите, как они обратно сливаются. То есть всё, что возможно, — что я, может быть, не так понятно и чётко объяснил здесь, в подкасте, — вы точно поймёте, увидев эту замечательную визуализацию. Спасибо Энди Павло: в своих лекциях он как раз мне это показал. И мне кажется, этот ресурс очень полезный, чтобы закрыть какие-то пробелы и недопонимания, потому что это знание понадобится. Дальше мы будем рассматривать более сложные структуры данных, и нужно понимать, как работает B+tree, потому что дальше будет сложнее.

[19:03] Итак, мы рассмотрели самую распространённую структуру в базах данных — B+tree. Распространение она получила за счёт того, что имеет высокую степень ветвления и низкую высоту, что снижает количество случайных чтений с диска и повышает число последовательных чтений. Это идеально подходит для работы с диском. К тому же внутренние узлы отлично ложатся на концепцию постраничной организации. Однако в чистом виде B+tree не так часто используется в современных хранилищах: с 1979 года появились более эффективные структуры данных, о них мы поговорим в следующем выпуске подкаста, который выйдет уже через неделю. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!