B-дерево
ฝัง
- เผยแพร่เมื่อ 9 ก.พ. 2025
- B‐дерево (произносится «би дерево») - это вид деревьев, который гарантирует полную балансировку. Не стоит путать его с бинарными деревьями, так как он с ними не имеет ничего общего.
В этом видео уроке я обсуждаю, что такое B‐дерево и как работает алгоритм добавления данных в него. Как пример я обсуждаю дерево с M=4, также известное как дерево 2‐3‐4.
Ты самый умный и уграный священник из всех, кого я видел)
Очень рад, что несмотря все виды горя, которые автору довелось пережить за эти 25 минут, на доске все еще оставалось Би-дерево
Вот к таким священникам надо на службу ходить. Спасибо вам . Очень доходчиво и понятно.
Отец, я не понимаю как устроены индексы в постгрес. Сын мой, этож битри деревья! Сейчас объясню.
Теперь я верую в B деревья! Автор, продолжай. Очень убедительно, с харизмой 👍
"Обычно у нас деревья растут сверху вниз... .... ... Не говорите биологам!" :D
Пользуюсь вашими видео, каждый раз когда готовлюсь к собеседованиям, спасибо за труд!
Иисус лично решил спуститься с небес, что б пояснить за B деревья... Воистину лучший
Дай Бог Вам здоровья, мне так понравилось ваше объяснение. Вы умничка спасибо Вам большое, Вы очень помогли
Мне кажется, что надо назвать твой канал: IT-Иисус. Это будет полностью соответствовать, т.к объясняешь ты, как боженька и очень похож на него)
особенно учитывая, что к середине я понял о чём речь, не смотря предыдущие ролики и будучи вообще не в теме ):
И положил он байты с битами по благой последовательности их, и приходили люди, и уверовали онлайн, и святость айтишная воцарилась в душах их, и кодили во славу цифровую до апгрейда их, и никакой баг не поразил их боле, ибо благословенны деяния их.
уже есть такой канал. Coding Jesus называется....
Крутая подача и ход мыслей, однозначно респект!
Лучшее объяснение этой темы из всех, что я видел. Большое спасибо, очень нравится Ваш канал. Очень качественные объяснения, да и просто приятно смотреть)
Бро это лучшее видео п о структурам данных которое я видел, большое человеческое спасибо
Спасибо Вам огромное, Владимир, за такое доходчивое объяснение темы!
Добрый день!
Благодарю Вас что записали это видео
Спасибо, сразу стало понятно как работают b-деревья
Отличное объяснение! Этим и отличается хороший учитель: простым и доходчивым языком донести сложную тему! Спасибо!
Ещё было бы здорово сравнить с B+ деревом, чтобы не путать их. Ведь B+ дерево тоже относится к сбалансированным, но имеет свои нюансы.
Владимир спасибо Вам за ваши лекции по алгоритмам и структурам данных. Очень приятно,в красках, доходчиво преподносите материал! Успехов Вам и развития!)
Как обычно от нечего делать хотел оставить какой-нибудь язвительный комментарий в интернете, сделав это под видео. Но посмотрел все видео, - действительно классное объяснение, понял многие моменты работы B-деревьев (я не ходил в университет полтора года из-за работы и пропустил эту тему). Очень понравилось, круто, спасибо :)
Я еще диплом пишу, про самообучающуюся модель для 2d real-time игры с видом сверху;
Вот, я вообще нейронные сети использовал, но неделю назад посетила идея попробовать сделать обучение и хранение знаний в дереве.
Т.е. подается какой-то вектор состояний системы, которые вычисляет бот, на B-дерево знаний; Там по некоторым формулам идет приблизительный поиск подобного вектора в дереве; Если такой есть, то выполняются действия по закону, описанному в найденной ноде.
Если нода с таким вектором не найдена, то ожидаем результата действия (т.е., "встретить лицом снаряд танка", игра про танчики :D). Если результат негативный для бота, то в ноде это отражается как-то. Если положительный, то увеличивается.
Короче, я еще не реализовывал, т.к. нейронки мучаю
Как думаете, стоит ли издеваться над B-деревом таким способом?:) Или нейронные сети реализуют то же самое, но лучше в моей задаче?
Forged Spirit Ну нейронной сети всё равно где информация хранится. Можно делать и в B-дереве, алгоритму ведь будет всё равно. Тут более, как мне кажется, интересна будет сама функция обучения. Определить хорошо/плохо будет легко, а вот дать достаточное количество вводов, и затем прогнать достаточное количество раз... Хотя если вы делаете оба танка автоматическими и они начинают биться против друг друга, то второй вопрос решается. А по поводу первого, тут наверно проще просто экспериментально посмотреть.
Довольно страстное и выразительное изложение. Лайк
Спасибо, Владимир. Вы наш Павел Флоренский.
Мужик, ты очень крут! Спасибо большое!
Как чётко.. каждое слово в душу...
Спасибо за информативное и интересное видео!
Жаль не рассказал про удаление ключа
Из всего найденого в ютубе это видео самое доходчивое.
Крутой видос, спасибо!
Спасибо, Володя, за лекцию!
"не говорите биологам" в голос. однозначно лайк
бро, очень круто объяснл, от души спасибо
Идеально!!! Все просто и понятно , спасибо!!
В классической версии при переполненности корня он расщепляется сразу же, без попытки определить ключ в дочернюю ноду, это делается для упрощения алгоритма, чтобы не делать лишних действий
Получается что состояние в 18:13 невозможно
Но я соглашусь что эта оптимизация скорее может запутать, поэтому Володя о ней тут не говорит
Здравствуйте. Вы очень хоршо и доходчиво объясняите.
Мне кажется или на 15 минуте вы "16" подвинули вверх, но 48 так и не добавили? Или я что то не так понял?
А так спасибо Вам большое, был бы рад если бы вы продолжали и разобрали к примеру красно-черное дерево=)
А вот вопрос кстати очень интересный. Потому что он по идее того должен был поменять местами 23 и 43, так как нода получалась не сортированной.
@@pyramidhead9692 48 просто запишется правее 23, так же как записывались 13 и 5 в самом начале.
Огромное, огромное и еще раз огромное спасибо!!! Очень помогло!!!
классно! наглядно понятно и с примером!
"Обычно у нас растут деревья сверху вниз"... далее лицо Володи....
Спасибо за лекцию.
Когда смотришь видео айти-батюшки 8-летней давности...
Без шуток,объяснятешь ты как боженька)
Очень хорошо объяснено!
Так бы в универе преподавали. Спасибо огромное!
Отлично объяснил! Спасибо огромное)
Очень рад, что помог. Это весьма сложная структура, мне понадобилось очень много времени для выяснения сути происходящего. Обычно всё объясняют математически, и приходится очень долго вникать, чтобы понять весьма простые вещи.
Это точно, уж очень бывает перегибают. www.cs.usfca.edu/~galles/visualization/Algorithms.html Тут хорошо интерактивно можно въехать в суть, но блин без понятной теории это тоже тяжело даётся:)
Хотелось бы предварительно осветить понятия бинарного дерева и нода, а потом уже переходить к B-деревьям. Излагаете хорошо.
Спасибо за отличное видео.
1:54 максимальное количество значений в B-дереве M - это количество ключей в узле, или высота дерева?
Разжевал, так разжевал! Спасибо тебе мужик!
Thanks, Jesus, very informative !
Хорошо объяснил, очень доходчиво!
Но, не лишним было бы рассказать и про удаление элементов, доступ к элементам.
Спасибо, Владимир, все доходчиво и понятно на примере. Про 48 все ясно - оно максимально и роли не играет, нечаянно пропустили. Возник другой вопрос - Вы говорите, что при M=2 дерево будет бинарным. Если не изменяет память, то в бинарном дереве количество потомков НЕ БОЛЕЕ двух, т.е. включая 1. Но ведь это не верно для B-деревьев при M=2? Или я что-то напутал?
шикарно обьяснил
Лучших объяснений не видел
Спасибо, отец
Насчет числа 48, это он случайно пропустил :) Просто представьте, что мы провернули все это для числа 15, то есть наша последовательность выглядит так: 8,13,5,0,16,7,23,15, суть от этого не меняется.
Отличное видео, спасибо
а если у нас M это нечетное число, тогда максимальное количество ключей/значений в узле будет четным, как в этом случае нам делать "разделение" узла (когда мы брали ключ/значение в узле посередине, "поднимали" его на уровень выше, а соседние ключи/значения разделяли)
То есть, какой ключ/значение из узла нам нужно "поднимать" на уровень выше?
Надеюсь понятно сформулировал вопрос
Спасибо, классное видео!
Пожалуйста объясните как так получилось что если м=4 на левой стороне в самом нижнем уровне оказалось 4 нод а не 3? Ведь по правилам В деревьев должно быть не больше или равно м-1?
спасибо большое
Вообще ничего не понял. Как так получается, что на верхнем уровне 3 значения, а на нижнем больше 4 нод, если сами говорили про количество значений+ 1?
Спасибо огромное!!!
Когда мы 0 добавляли, то получается, что мы как бы не крайние элементы вниз убирали, а наоборот центральный наверх, судя по дальнейшей логике добавления.
Где эти деревья интересно используются
С удалением записи из узла никак разобраться не получается. Не пойму, как должна происходить балансировка
При разрыве берётся центральное или среднее? Просто если есть 2 ключа, то и центрального там не будет
Огонь чувак
Спасибо! Помогло.
а где делось число 48?
проебали
Пожелание - очень хочется понять знания из области аналитической механики. Спасибо!
Подписался!
Благодарю!
Вы говорите что можно сбалансировать Btree дерево с М = 2. Но ведь для этого придется добавлять сразу по два значения в дерево. Иначе оно не будет сбалансированным. Другими словами - Btree дерево можно полностью сбалансировать только если в нем нечетное кол-во значений, я правильно понимаю?
+Yauheni Neshyn Нет, оно балансируется обязательно всегда, с любым количеством значений. Вы просто сбросите одно значение из корня вниз.
Я не понял вот что. Индексы в оракле - сбалансированные деревья. Но какой у них тогда уровень?
Спасибо за экскурс по b-деревьям. Но как же удалять элементы из b-деревьев?
Если нужно удалить, то горе нам!
Там нужно у правых сыновей красть по ситуации.
Спасибо завашу работу. У меня один вопрос. Вы говорили про то, что указаталей может быть либо 0, либо 6. Что имело ввиду, так как по факту вы показали иначе. Спасибо!
Я это понял иначе. Если у тебя есть блок с 5 значениями, то на следующем уровне у тебя будет либо 0 нод либо 6
Володя, спасибо за объяснение!
Скажите пожалуйста, а не могли бы вы объяснить как работают B+ деревья?
Благодарю.
+Eugene Pashkevich С ними не работал, но может узнаю и запишу если будет муза )))
забыли сказать что фактор для нижних уровней должен быть 2t-1, чтобы при разбиении в случае заполнения разбивалось на два равных ноды, и оставался один элемент для переноса вверх
Ребят, не очень понял на 8:40 - 9:00
Почему максимум может быть 4 дочерних ноды и максимум 3 значения?
Как я понял, M=4 означает, что 4 указателя, от одного указателя 1 дочерна , поэтому и 4 дочерних.
А в 4 указателя можно вписать только 3 значения, потому-что нужно, чтобы указатели окружали их с обоих сторон.
Возможно уже поздно, но всё же
Снял бы для полноты картины и про Dancing tree
Подскажите, пожалуйста, может кто-либо знает:
"Как найти элемент В-дерева, предшествующий данному ключу?"
Почитав несколько ресурсов про b-tree, я ни где не встречал такого обозначения как "M" (уровень). Везде (например, wiki) фигурирует некий параметр "t", от которого зависит количество ключей в ноде (при этом, в корне и в узлах, разные ограничения на количество ключей). Поясните, пожалуйста, существует ли какая-то зависимость между t и M?
+Alexander Kuleshov Может это из-за того, что я постоянно на английском всё читаю. В англоязычной википедии есть m - максимальное количество дочерних узлов, но они её сделали мальнькой. en.wikipedia.org/wiki/B-tree#Definition
Не стоит заострять внимание на том, какая буква используется. Можно было взять что-то из греческого, еврита, арабского, да даже кириллицы, смотря на русскую википедию мне кажется тут о том-же самом говорят. Сколько может быть "ссылок" на дочерние элементы у данного.
Дело в том, что и в англоязычной и в русскоязычной википедии, да и в книгах с теорией о B-деревьях говорится, что если уровень дерева M, то количество ключей в узле может быть от 1 до 2*М-1. Из вашего видео ясно видно, что количество ключей в узле не превышает М-1. Тут получается расхождение, совсем разные деревья получатся... Так где же правда?:)
@@MrGOODlikerНашел годньй пример дерева www.geeksforgeeks.org/delete-operation-in-b-tree/?ref=lbp
// Allocate memory for maximum number of possible keys
// and child pointers
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
там бьла эта строчка отсюда получаетса что t это количество значений и указателей в одном узле.
Благодарю
Спасибо!
Гений!
а как смещаются элементы при m=5?
Спасибо
А все-таки, куда у вас делось число 48?
А что по поводу удаления из B-дерева?
Борода потерял 48 где-то по дороге
Прошу пояснений 4.10 говорим количество нод 0 или разрядность дерева. В дальнейшем слышу может быть меньше. Противоречие
а как би-дерево может быть бинарным, если в нем 2 элемента?
Владимир, напишите в комментарии куда вы 48 вставили!
А почему вы добавили 7 именно на конец левого узла, а не в начало правого, потому что 7 ближе к 5-и чем к 13-и?
Потому что в правом узле хранились значения не меньше 8
Спасибо тебе, бородатый Итан Хоук
Хм... Всё ещё не понял что это за деревья такие, как с ними работать и как это работает в БД
Что насчет удаления? Будет видео?
А куда делось число 48?
Не знал, что Джаред Лето... разбирается в теории алгоритмов.
Раздражает постоянное перебирание фломастеров + это тормозит. Пожалуйста, используйте 1 цвет или хотя бы колпачок не закрывайте
во наглая
Если кто не знал, узлы он называет нодами(лично я не слышал про такое), иб тоже кто то затупил
не рассказанная глава Евангелие, пишники ставьте лайк, если вы от рамона
Воистину, едины в Залупиносе....
а 48 почему-то и не вставили
пушка