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

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

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

Спасибо!

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

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

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

Найс!

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

@Max-wn2gd

3 ай бұрын

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

@ntvisigoth

3 ай бұрын

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

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)

B это balanced