Как устроен B-TREE индекс в базах данных

Записи реальных собесов и полезную инфу для подготовки можно найти на бусти boosty.to/vanyaio
Первое видео: ИНДЕКСЫ В БАЗАХ ДАННЫХ. СОБЕС В OZON • ИНДЕКСЫ В БАЗАХ ДАННЫХ...
Третье видео: EXPLAIN в базах данных за 10 минут boosty.to/vanyaio/posts/1de60...
0:00 Начало
1:12 B-дерево
2:12 Поиск в дереве
4:55 Поиск в диапозоне
5:52 Листья отсортированы
6:22 Сбалансированность
7:35 Вопросы с собеседований
10:29 Что лежит в листьях индекса
12:38 Индекс и ORDER BY
14:07 Составные индексы
16:00 Почему такое правило

[@exynos328]

Спасибо большое за наглядные объяснения, как раз готовлюсь к собесу сейчас, очень помогаешь! :)

[@user-ir4vd5yk4x]

посмотрел фулл. спасибо за годноту

[@planchet2013]

Легенькая база, для того, чтобы понять основу - отлично. Спс

[@vova_dev]

Спасибо!

[@sashas.3323]

о , у меня такое как то на собесе спрашивали , я ответил , что-то вроде того , что поиск происходит как при бинарном поиске

[@dadagj728]

8:57 количество уровней - это не логарифм от количества листьев. количество уровней определяется коэффициентом ветвления (branching factor) - количеством дочерних узлов у одного узла, и равно «количество узлов/коэффициент». логарифм - это сложность для такого дерева, и это не логарифм по основанию 2, как мы привыкли думать о «логарифме», а логарифм по основанию «коэффициент», а если ещё точнее, то О(коэффициент*[логарифм(n) по основанию коэффициент])

[@ivangolang]

Я не понимаю почему высота дерева, это то, что вы написали. В вики и прочих источниках вижу оценки высоты через логарифмы и число узлов. Ну а число узлов на самом деле грубо оценивается числом листьев, для O не принципиальный момент.

[@krl4kk]

log - это сложность поиска по такому дереву. количество уровней b-tree - это не просто log

[@ivangolang]

@@krl4kk сложность поиска разве не определяется числом уровней?

[@krl4kk]

в моем понимании сложность поиска определяется количеством элементов и она равна logN, а высота logmN(m - степень ноды, количество элементов в одной ноде). если бы этого условия не было, то было обычное самобалансирующееся дерево и никаких плюшек для хранения на диске не было

[@ivangolang]

Спасибо за комменты, давайте просто с итмошных вики-коспектов оставлю оценки B-дерево (англ. B-tree) - сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за O(logn). B-дерево с n узлами имеет высоту O(logn)

[@nikolaykozlov4888]

Вань, привет! И всем - привет!

[@yashkevich8164]

Б-Три индекс - это специальное сбалансированное отсортированное дерево, которое в отличие от большинства стандартных деревьев растет в ширь(на диске данные ближе друг к другу), а не в глубину. В общем для этого индекса дерево как бы свое специальное. Вот вкратце суть.

[@user-ge6pt5lp9u]

Найс!

[@krl4kk]

клевый видос, спасибо! не хватило объяснения зачем же вообще нужно b-tree, если есть обычные бинарые деревья. разница между дисковыми структурами и структурами для памяти. а также вставки и удаления, но тогда бы наверное затянулся бы))

[@Max-wn2gd]

Про разницу про структуры не понял. Бинарное дерево легко можно реализовать на основе массива и работать будет быстро

[@ntvisigoth]

Обычное бинарное дерево состоит из узлов, в котором не более чем одного элемента. Так ведь? К примеру, есть узел со значением 7, а у него есть дочерние : левый со значением 3 и правый со значением 9. Когда нам удобно с этим работать? Тогда, когда это дерево находится в памяти. А зачем нужна нам БД, если она только и только в памяти хранит свое состояние? То есть нам нужна БД, которая отвечает букве D в акрониме ACID. Долговечность! За это свойство отвечает дисковое хранилище. А вот когда дерево , обычное, находится на диске, то мы получаем такую же скорость, как если бы оно находилось в памяти? Нет! Потому что позиционирование головки, чтение головки и др. это долго. Что тогда делать? Тогда надо сделать дерево медленно растущим в глубину, но при этом растущее в ширь. Именно по этой причине, каждый узел B-дерева резервирует место в узлах, чтоб уметь содержать более чем один элемент. Ведь тогда, мы можем уменьшить кол-во операций по позиционированию головок, ведь элементы в узле отсортированы. Рекомендую к прочтению: - Рогова "Postgres Internals 15" - или статью habr.com/ru/articles/783012/ "Почему B-деревья быстрые?"

[@user-zw9jh8te9c]

B это balanced