Бази даних і структури даних / крок 03
Дерева. Пошук. Алгоритми. Бази даних
Про що це відео
«Місткове» відео біля дошки, яке автор свідомо зробив як підготовку до свого глибокого розбору індексів MySQL проти Postgres: які деревоподібні структури даних бази даних насправді використовують усередині індексів і чому. Починаючи з таблиці товарів, він нагадує, що відсортована копія колонки вмикає бінарний пошук — його повторюване число: 100 трильйонів записів шукаються за ~46 поділів навпіл замість 100 трильйонів кроків (алгоритмічна складність) — але відсортований масив робить вставку O(N), тож потрібні дерева. Він малює бінарне дерево пошуку («все, що ліворуч від 7, менше, все праворуч — більше») і показує його пастку: вставте 1,2,3,4,5 по черзі — і BST вироджується у зв'язний список із пошуком O(N), звідси самобалансовані варіанти на кшталт AVL-дерев, які обертають вузли при вставці, тримаючи різницю висот лівого/правого піддерев у межах 1. Далі ключовий аргумент: бази даних усе одно не використовують бінарні дерева, бо на 100 млн записів дерево має ~23 рівні, і якщо кожен рівень коштує disk seek (~5 мс на шпиндельному диску), 23×5 мс — надто повільно. B-дерево дає кожному вузлу багато дітей — у Postgres/MySQL вузол має розмір дискового блока (наприклад, 8 KB), що дає приблизно 200–2000 дітей на вузол — і глибина падає з ~23 рівнів до ~4, а то й 2 читань із диска. Наостанок він пояснює, чому бази даних використовують модифікацію B+ дерево: дані живуть лише в листових вузлах, а листи вказують одне на одного зв'язним ланцюжком, тож діапазонні запити («ціна від 100 до 110») і повні скани індексу просто йдуть уздовж листів, не стрибаючи вгору-вниз по дереву.
Головне
- Індекс — концептуально скопійована й відсортована колонка; одну таблицю не можна тримати відсортованою одночасно за назвою і ціною, тож кожен індекс — окрема відсортована структура (індекси).
- Відсортовані дані дають бінарний пошук за O(log N) — 100 трильйонів записів за ~46 кроків — але вставка у відсортований масив коштує O(N), і саме тому потрібні дерева (складність).
- Звичайне бінарне дерево пошуку вироджується у зв'язний список (його приклад: вставка 1..5 по черзі — кожен вузол чіпляється справа), і пошук стає O(N); збалансовані варіанти (AVL і компанія) обертають вузли під час вставки, щоб висота дерева була мінімальною (структури даних).
- Бази даних відкидають бінарні дерева з апаратної причини: ~23 рівні глибини на 100 млн рядків × ~5 мс на disk seek — надто повільно; вузол B-дерева розміром із дисковий блок (8 KB, ~200–2000 дітей) зрізає глибину до ~4 рівнів, іноді 2.
- B+ дерева (те, що бази даних реально використовують) тримають дані лише в листах і зшивають листи в ланцюжок, тож діапазонні скани («ціна 100–110») ідуть по ланцюжку листів без повторного спуску по дереву.
- Свідомо на рівні концепцій: механіку обертань/розбиттів він пропускає — «важливо зрозуміти, як це формує поведінку бази даних» — як підготовку до відео Як працюють індекси в базах на прикладі: MySQL vs Postgres, UUID vs Auto Increment.
- Тизер: файлові системи використовують ті самі ідеї — ext4 індексує файли H-деревом, спрощеним аналогом B-дерева; k-nearest / quadtree обіцяні як майбутні теми.