Індекс B+ Tree в базі даних

Чому це B+ дерево, а не просто B-дерево

Звичайне B-дерево дозволяє зберігати пару ключ-значення в будь-якому вузлі – внутрішньому чи листіть – відразу після введення ключа та коли у вузлі є місце. B+ дерево змінює це правило двома способами. По-перше, внутрішні вузли містять лише копії ключів, які використовуються для маршрутизації; вони ніколи не містять фактичне навантаження запису. По-друге, кожен реальний запис, разом із повним ключем, живе в листі, і тільки в листі. Коли ключ вводиться, дерево завжди йде вниз до листа, щоб розмістити його, і якщо цей ключ також повинен з’явитися у внутрішньому вузлі як роздільник, то лише копія ключа подорожує вгору, а не дані самі по собі. Це розмежування має практичний ефект: внутрішні вузли стають значно меншими на кожен ключ, оскільки вони не несуть навантаження, тому більше ключів маршрутизації поміщається на одну сторінку диска або в блок пам’яті. Компактне та широке дерево означає менше рівнів, які потрібно пройти до досягнення листка, і менше рівнів означає менше дорогих випадкових доступів з диска. У класичному B-дереві навантаження, змішане з внутрішніми вузлами, роздуває їх і змушує дерево вищими для тієї ж кількості даних. Друга визначальна риса, на яку зосереджується ця лабораторія, полягає в тому, що листки з’єднані між собою впорядкованим ключем, зазвичай у вигляді подвійного посилання, щоб сканування могло проходити вперед або назад. Цей зв'язок невидимий у простому B-дереві; там листки ізольовані

мертві кінці

і переміщення від одного листа з даними до іншого впорядкованого листа з даними означає підйом назад до спільного предка та вниз знову. У B+ дереві цей підйом непотрібний. Дерево спускається точно один раз, щоб знайти перший відповідний лист, і все після цього – прямий рух вздовж ланцюга. Спробуйте побудувати дерево в цій лабораторії та зверніть увагу на те, що, незалежно від того, наскільки глибоко воно росте, листки завжди залишаються зшитими ліворуч направо у порядку зростання.

Чому список з’єднаних листків змінює все для пошуку діапазонів

Уявіть запит, який запитує всі транзакції з певною датою між двома іншими датами. У структурі без з’єднаних листків задоволення цього запиту означає знайти перший відповідний ключ, а потім повторно ставити запитання дереву: яке наступне? Кожне з цих питань може вимагати повернення до кореня та повернення вниз різними шляхами, оскільки наступний ключ в порядку не обов’язково є сусідом у тому ж вузлі. Для діапазону, що охоплює тисячі рядків, це призводить до великої кількості перевірок дерева, кожна з яких може бути випадковим читанням диска. Дерево B+ видаляє майже весь цей шум. База даних виконує одноразову спуск для пошуку листка, що містить перший ключ, більший або рівний початку діапазону. Відтоді воно просто слідує за наступним покажчиком листа, читаючи записи в відсоркованому порядку, поки не досягне ключа, який перевершує кінець діапазону. Кожен крок — це дешевий послідовний рух до сусіднього листка замість свіжої перевірки дерева. На обертаючих дисках це мало значення; послідовні читання були набагато швидшими, ніж випадкові, а на сучасних твердотільних накопичувачах ця різниця менша, але все одно реальна, і зменшення кількості операцій ЦП (менше порівнянь, менше переслідування покажчиків через внутрішні вузли) залишається значним незалежно від цього. Механізм охоплює те саме для прискорення повних сканувань індексів та виведення даних у відсортованому порядку. Планувальник запитів часто хоче дані в ключовому порядку, щоб задовольнити клаузу ORDER BY, щоб живити з’єднання типів або обчислювати агрегацію над вікном рядків. Замість сортування даних окремо після отримання, двигун може просто пройти ланцюг листків існуючого індексу та отримати відсортоване виведення практично безкоштовно. Саме тому функція з’єднання листків не є незначною детальною реалізацією; це часто єдина найбільша причина, чому дерево B+ перевершує просте дерево B у робочих навантаженнях баз даних.

Чому MySQL InnoDB та PostgreSQL обирають B+ дерева

Основний механізм зберігання в InnoDB, який використовується за замовчуванням, будує індекс первинного ключа у вигляді B+ дерева, де самі листки містять повні дані рядка. Кожен додатковий індекс у InnoDB також є B+ деревом, але його листки зберігають значення індексованого стовпця плюс посилання на первинний ключ, а не повний рядок. У обох випадках зв’язність листів робить ефективними перевірки діапазону, такі як WHERE order_date BETWEEN X AND Y: двигун знаходить стартовий листок один раз і стікається вперед. PostgreSQL використовує подібний, але відмінний підхід. Його тип індексу за замовчуванням, оскільки він називається B-деревом, насправді реалізовано як B+ дерево всередині, з даними, що містяться на листі, пов’язаними через посилання між братами, також для підтримки ефективних перевірок діапазону, упорядкованих перевірок та навіть зворотних перевірок для спадних сортувань. Жодна з цих систем не використовує старішу структуру простого B-дерева для своїх щоденних індексів, оскільки виробничі робочі навантаження домінують точковими пошуками, змішаними з перевірками діапазону, і зв’язність листів добре підходить для обох. Є також додаткові переваги. Оскільки внутрішні вузли не містять даних, вони добре стискаються та схильні залишатися в пам'яті (буферному пулі або спільному кеші буферизації), тому дисковий доступ, який часто потрібен, - це лише рівень листка. Повні сканування таблиць, індексні скани без зачіпки до основної таблиці та масові операції експорту спираються на те саме переміщення по ланцюгу листів. Навіть звичайне обслуговування, таке як перебудова індексу або обчислення статистики, виграє від можливості стікатись через відсортовані дані без повторного пошуку дерева. Ця комбінація стислих маршрутів вузлів і відсортованих листів робить B+ дерево, а не класичне B-дерево, стандартним вибором для індексів реляційних баз даних.

Вставка, Розділення та Підтримка Послідовності

Вставку в B+ дерево починають так само, як і в звичайному B-дереві: спускаються від кореня, порівнюючи новий ключ із роздільними ключами у внутрішніх вузлах, поки не досягнуть відповідного листка. Ключ та його запис додаються до цього листка у відсортованому порядку. Якщо листок тепер містить більше записів, ніж дозволяє його ємність, він ділиться на два листки, кожен з яких містить приблизно половину записів. Тут B+ дерево відрізняється від класичного алгоритму важливим чином. Під час розділення внутрішнього вузла в звичайному B-дереві середній ключ переміщується до батьківського вузла та видаляється з дітей, оскільки ключі є унікальними для одного місця в дереві. У B+ дереві, коли листок ділиться, найменший ключ нового правої гілки копіюється (не переміщується) до батьківського вузла як роздільник; ключ все ще фізично залишається в листі разом зі своїм записом, оскільки листки повинні містити кожен ключ із своїм записом. Переміщаються лише тоді, коли внутрішній вузол ділиться. Надзвичайно важливо, щоб розділення оновлювало покажчики у зв’язному списку, щоб ланцюжок залишався неперервним: попередній покажчик нової правої гілки встановлюється на оригінальний листок, наступний покажчик оригінального листка перенаправляється на новий листок, а наступний покажчик нового листка бере на себе те, що раніше вказував оригінальний листок. Пропуск цього кроку бездумно зламає сканування діапазонів, які перетинають точку розділення, навіть якщо структура маршрутизації дерева над листками виглядає правильно. Якщо розділення поширюється вгору та навіть корінь ділиться, створюється новий корінь, який містить один роздільник ключа, і дерево стає на рівень вищим, але рівень листків і ланцюжок залишаються єдиним неперервним відсортованим рядком протягом усього часу. Використовуйте контроль вставки в цій лабораторії та спостерігайте, як покажчик між двома листками переконфігурується в момент розділення.

Видалення, ребалансування та реальні компроміси

Видалення ключа відбувається так само: спускається до листового вузла, що його містить, і запис видаляється. Якщо після цього листовий вузол все ще має щонайменше мінімальну кількість записів, нічого іншого не потрібно робити структурно, хоча розділовий ключ вище в дереві може бути трохи застарілим; більшість реалізацій це допускають, оскільки він все одно правильно маршрутизує пошуки, якщо залишається послідовним з межею між дітьми. Якщо видалення залишає листовий вузол недоповненим, дерево намагається позичити зайвий запис від сусіднього листового вузла, коригуючи розділовий ключ батьківського вузла відповідно. Коли позичання неможливе, оскільки сусід також досяг мінімуму, два листові вузли зливаються в один, і відповідний розділовий ключ батьківського вузла видаляється. Як і при розгалуженнях, ця бухгалтерія легко зробити неправильно у відсутній з нуля, і зламаний покажчик може призвести до безшумного пропуску даних або циклу сканування діапазонів, навіть якщо пошук за точками через дерево все одно буде успішним. Обмін, який приймають бази даних для всього цього, це деяке дублювання зберігання ключів, оскільки розділові ключі в внутрішніх вузлах є копіями ключів, які також живуть у листах, і кожен лист несе два додаткових покажчики для своїх сусідів. В обмін на це вони отримують майже постійний час доступу до наступного або попереднього запису в відсортованому порядку, стійку підтримку як рівності, так і предикатів діапазонів через одну й ту ж структуру та внутрішні вузли, які достатньо компактні, щоб більшість дерева зберігалася в пам'яті. Це компроміс, який кожне виробництво двигун бази даних вважає вартим, тому що незважаючи на прізвище, це B+ дерево, а не оригінальне B-дерево, виконує справжні роботи в індексі, який ви запитуєте кожного дня.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте B+ Tree Database Index і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.