Записи реальных собесов и полезную инфу для подготовки можно найти на бусти boosty.to/vanyaio Тренажер по Go для подготовки к собесу: stepik.org/a/206788 Задачи на горутины и каналы Go для собесов: stepik.org/a/207625
клевый видос, спасибо! не хватило объяснения зачем же вообще нужно b-tree, если есть обычные бинарые деревья. разница между дисковыми структурами и структурами для памяти. а также вставки и удаления, но тогда бы наверное затянулся бы))
Обычное бинарное дерево состоит из узлов, в котором не более чем одного элемента. Так ведь? К примеру, есть узел со значением 7, а у него есть дочерние : левый со значением 3 и правый со значением 9. Когда нам удобно с этим работать? Тогда, когда это дерево находится в памяти. А зачем нужна нам БД, если она только и только в памяти хранит свое состояние? То есть нам нужна БД, которая отвечает букве D в акрониме ACID. Долговечность! За это свойство отвечает дисковое хранилище. А вот когда дерево , обычное, находится на диске, то мы получаем такую же скорость, как если бы оно находилось в памяти? Нет! Потому что позиционирование головки, чтение головки и др. это долго. Что тогда делать? Тогда надо сделать дерево медленно растущим в глубину, но при этом растущее в ширь. Именно по этой причине, каждый узел B-дерева резервирует место в узлах, чтоб уметь содержать более чем один элемент. Ведь тогда, мы можем уменьшить кол-во операций по позиционированию головок, ведь элементы в узле отсортированы. Рекомендую к прочтению: - Рогова "Postgres Internals 15" - или статью habr.com/ru/articles/783012/ "Почему B-деревья быстрые?"
8:57 количество уровней - это не логарифм от количества листьев. количество уровней определяется коэффициентом ветвления (branching factor) - количеством дочерних узлов у одного узла, и равно «количество узлов/коэффициент». логарифм - это сложность для такого дерева, и это не логарифм по основанию 2, как мы привыкли думать о «логарифме», а логарифм по основанию «коэффициент», а если ещё точнее, то О(коэффициент*[логарифм(n) по основанию коэффициент])
Я не понимаю почему высота дерева, это то, что вы написали. В вики и прочих источниках вижу оценки высоты через логарифмы и число узлов. Ну а число узлов на самом деле грубо оценивается числом листьев, для O не принципиальный момент.
в моем понимании сложность поиска определяется количеством элементов и она равна logN, а высота logmN(m - степень ноды, количество элементов в одной ноде). если бы этого условия не было, то было обычное самобалансирующееся дерево и никаких плюшек для хранения на диске не было
Спасибо за комменты, давайте просто с итмошных вики-коспектов оставлю оценки B-дерево (англ. B-tree) - сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за O(logn). B-дерево с n узлами имеет высоту O(logn)
Б-Три индекс - это специальное сбалансированное отсортированное дерево, которое в отличие от большинства стандартных деревьев растет в ширь(на диске данные ближе друг к другу), а не в глубину. В общем для этого индекса дерево как бы свое специальное. Вот вкратце суть.
Записи реальных собесов и полезную инфу для подготовки можно найти на бусти boosty.to/vanyaio
Тренажер по Go для подготовки к собесу: stepik.org/a/206788
Задачи на горутины и каналы Go для собесов: stepik.org/a/207625
Это видео очень помогло разобраться почему индексы работают до первого неравенства и как они работают с составным индексом. Спасибо большое!!!
Спасибо большое за наглядные объяснения, как раз готовлюсь к собесу сейчас, очень помогаешь! :)
посмотрел фулл. спасибо за годноту
Отличная просто информация - ОТЛИЧНАЯ!!!! Спасибо тебе!
чел, ты гений!!!! Это самое шикарное что я видел.
Отличное видео! спасибо Вам огромное за понятное объяснение!
Легенькая база, для того, чтобы понять основу - отлично. Спс
клевый видос, спасибо!
не хватило объяснения зачем же вообще нужно b-tree, если есть обычные бинарые деревья. разница между дисковыми структурами и структурами для памяти. а также вставки и удаления, но тогда бы наверное затянулся бы))
Про разницу про структуры не понял. Бинарное дерево легко можно реализовать на основе массива и работать будет быстро
Обычное бинарное дерево состоит из узлов, в котором не более чем одного элемента. Так ведь?
К примеру, есть узел со значением 7, а у него есть дочерние : левый со значением 3 и правый со значением 9.
Когда нам удобно с этим работать? Тогда, когда это дерево находится в памяти.
А зачем нужна нам БД, если она только и только в памяти хранит свое состояние? То есть нам нужна БД, которая отвечает букве D в акрониме ACID. Долговечность! За это свойство отвечает дисковое хранилище.
А вот когда дерево , обычное, находится на диске, то мы получаем такую же скорость, как если бы оно находилось в памяти? Нет! Потому что позиционирование головки, чтение головки и др. это долго. Что тогда делать? Тогда надо сделать дерево медленно растущим в глубину, но при этом растущее в ширь.
Именно по этой причине, каждый узел B-дерева резервирует место в узлах, чтоб уметь содержать более чем один элемент. Ведь тогда, мы можем уменьшить кол-во операций по позиционированию головок, ведь элементы в узле отсортированы.
Рекомендую к прочтению:
- Рогова "Postgres Internals 15"
- или статью habr.com/ru/articles/783012/ "Почему B-деревья быстрые?"
Вань, привет! И всем - привет!
8:57 количество уровней - это не логарифм от количества листьев.
количество уровней определяется коэффициентом ветвления (branching factor) - количеством дочерних узлов у одного узла, и равно «количество узлов/коэффициент».
логарифм - это сложность для такого дерева, и это не логарифм по основанию 2, как мы привыкли думать о «логарифме», а логарифм по основанию «коэффициент», а если ещё точнее, то О(коэффициент*[логарифм(n) по основанию коэффициент])
Я не понимаю почему высота дерева, это то, что вы написали. В вики и прочих источниках вижу оценки высоты через логарифмы и число узлов. Ну а число узлов на самом деле грубо оценивается числом листьев, для O не принципиальный момент.
log - это сложность поиска по такому дереву.
количество уровней b-tree - это не просто log
@@krl4kk сложность поиска разве не определяется числом уровней?
в моем понимании сложность поиска определяется количеством элементов и она равна logN, а высота logmN(m - степень ноды, количество элементов в одной ноде).
если бы этого условия не было, то было обычное самобалансирующееся дерево и никаких плюшек для хранения на диске не было
Спасибо за комменты, давайте просто с итмошных вики-коспектов оставлю оценки
B-дерево (англ. B-tree) - сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за O(logn). B-дерево с n узлами имеет высоту O(logn)
Б-Три индекс - это специальное сбалансированное отсортированное дерево, которое в отличие от большинства стандартных деревьев растет в ширь(на диске данные ближе друг к другу), а не в глубину. В общем для этого индекса дерево как бы свое специальное. Вот вкратце суть.
крутой видос, спасибо
Спасибо!
о , у меня такое как то на собесе спрашивали , я ответил , что-то вроде того , что поиск происходит как при бинарном поиске
Бинарный поиск - ваще не то же. )))) Бинарный поиск - это в массиве за O(log2(N)) делением пополам.
Видос заебись, но с качеством проблемы, оч плохо видно на 17 минуте, пили хотя бы в FHD
Не знал, что шиша из топ дог шарит за индексы😂
Огромное спасибо! Жаль что ты не шарпист. Подписался бы на бусти тогда.
Найс!
B это balanced