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

Рет қаралды 3,610

Күн бұрын

Записи реальных собесов и полезную инфу для подготовки можно найти на бусти 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 Почему такое правило

Пікірлер: 19

@exynos328 3 ай бұрын

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

@user-ir4vd5yk4x 3 ай бұрын

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

@planchet2013 Ай бұрын

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

@nikolaykozlov4888 3 ай бұрын

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

@vova_dev Ай бұрын

Спасибо!

@sashas.3323 3 ай бұрын

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

@yashkevich8164 3 ай бұрын

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

@krl4kk 3 ай бұрын

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

@Max-wn2gd 3 ай бұрын

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

@ntvisigoth 2 ай бұрын

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

@user-ge6pt5lp9u 3 ай бұрын

Найс!

@dadagj728 3 ай бұрын

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

@ivangolang 3 ай бұрын

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

@krl4kk 3 ай бұрын

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

@ivangolang 3 ай бұрын

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

@krl4kk 3 ай бұрын

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

@ivangolang 3 ай бұрын

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