Довідка та теорія
B-дерево — це збалансоване багатошляхове дерево пошуку. Кожен вузол містить впорядкований ряд ключів і вказівники на нащадків між ними, тож один вузол може мати багато нащадків.
Правила порядку m
- Вузол має щонайбільше
mнащадків. - Вузол містить щонайбільше
m−1ключів. -
Некореневий вузол містить щонайменше
⌈m/2⌉−1ключів. - Усі листки на однаковій глибині.
Вставка та розщеплення
Ключі вставляються в потрібний листок. Якщо вузол
переповнюється до m ключів, він
розщеплюється: медіана рухається вгору до батька,
а решта стає двома сусідами. Розщеплення кореня нарощує дерево на
рівень — згори, ніколи знизу.
Чому воно лишається збалансованим
Оскільки дерево росте лише через підняття медіани вгору, кожен
шлях від кореня до листка тримає однакову довжину. Висота росте
як log⌈m/2⌉(n), тож навіть мільйони
ключів лежать на кількох рівнях.
Де воно застосовується
B-дерева та B+ дерева лежать в основі індексів реляційних баз даних і файлових систем, де неглибоке дерево означає мало повільних читань дискових сторінок на пошук.
Як працює ця симуляція
Це справжнє B-дерево, а не записана анімація. Оберіть
порядок m від 3 до 6, потім вставляйте ключі. Кожен ключ
спускається до потрібного листка, використовуючи впорядковані ключі в
кожному вузлі як дороговкази. Коли вузол заповнюється до
m ключів, він розщеплюється по медіані:
медіанний ключ підіймається до батька, а решта ключів утворюють двох
сусідів. Якщо розщеплюється сам корінь, з'являється новий корінь, і
все дерево набуває рівня згори, через що кожен листок завжди лишається
на однаковій глибині.
Як читати полотно
Кожен вузол малюється як коробка з упорядкованими ключами, від проміжків між якими спускаються вказівники нащадків. Найновіше розщеплення підсвічується, тож ви можете простежити, куди пішла медіана й як утворилися два нові сусідні вузли. Панель статистики показує живі порядок, висоту, кількість вузлів, загальні ключі та поточну кількість розщеплень. Спробуйте малий порядок, як-от 3, щоб часто викликати розщеплення, або скористайтеся Випадковий, щоб швидко заповнити дерево.
Поширені запитання
Що таке B-дерево?
B-дерево — це самобалансивне багатошляхове дерево пошуку. Кожен вузол може містити багато ключів і багато нащадків, а всі листки лишаються на однаковій глибині, тож пошук, вставка та видалення — O(log n) з дуже малою кількістю відвідувань вузлів, що ідеально для дискового й сторінкового зберігання.
Що означає порядок m?
Порядок m — це максимальна кількість нащадків, яку може мати вузол. Вузол порядку m містить щонайбільше m−1 ключів і, якщо це не корінь, щонайменше ceil(m/2)−1 ключів. Ця симуляція дозволяє обрати m від 3 до 6.
Як працює розщеплення?
Коли вузол переповнюється m ключами, він розщеплюється: медіанний ключ проштовхується вгору до батька, а решта ключів стають двома сусідніми вузлами. Якщо розщеплюється корінь, створюється новий корінь і дерево росте на один рівень угору.
Чому всі листки лишаються на однаковій глибині?
B-дерево росте у висоту лише через розщеплення кореня й проштовхування ключа вгору. Оскільки розщеплення поширюються вгору й ніколи не подовжують одну гілку окремо, кожен шлях від кореня до листка завжди має однакову довжину, тримаючи дерево ідеально збалансованим за висотою.
Як виконується пошук у B-дереві?
Пошук сканує впорядковані ключі всередині вузла, щоб знайти проміжок, у який потрапляє ціль, потім слідує вказівнику нащадка для цього проміжку й повторює, спускаючись на один рівень за вузол, доки ключ не знайдено або не досягнуто листка без нього.
Чому B-дерева використовують для індексів баз даних?
Оскільки кожен вузол вміщає багато ключів, дерево дуже неглибоке, тож пошук торкається лише жменьки вузлів — а отже, жменьки дискових сторінок. Це мінімізує повільні читання з диска, тому B-дерева та їхній варіант B+ дерево лежать в основі майже кожного індексу реляційних баз даних і багатьох файлових систем.
У чому різниця між B-деревом і B+ деревом?
У B-дереві кожен вузол може зберігати значення даних. У B+ дереві всі значення живуть у листках, а внутрішні вузли містять лише маршрутні ключі, причому листки з'єднані в список. Це полегшує діапазонні сканування, тому більшість баз даних насправді використовують B+ дерева.
Наскільки високим стає B-дерево?
Висота росте з логарифмом кількості ключів за основою ceil(m/2). За великого порядку m дерево, що містить мільйони ключів, може мати лише три-чотири рівні, що саме й робить його таким ефективним на диску.
Що симуляція підсвічує після розщеплення?
Підсвічується вузол, що нещодавно розщепився, і ключ, проштовхнутий угору до його батька, тож ви можете простежити, як рухалася медіана і як утворилися два сусідні вузли.
Чи це справжня реалізація B-дерева?
Так. Вставка використовує стандартний алгоритм розщеплення при переповненні з проштовхуванням медіани. Ключі тримаються впорядкованими в кожному вузлі, всі листки лишаються на однаковій глибині, а порядок, висота, кількість вузлів і кількість розщеплень оновлюються наживо зі справжньої структури.