B-дерево
B‐дерево (произносится «би дерево») - это вид деревьев, который гарантирует полную балансировку. Не стоит путать его с бинарными деревьями, так как он с ними не имеет ничего общего.
В этом видео уроке я обсуждаю, что такое B‐дерево и как работает алгоритм добавления данных в него. Как пример я обсуждаю дерево с M=4, также известное как дерево 2‐3‐4.
Пікірлер: 136
Ты самый умный и уграный священник из всех, кого я видел)
Очень рад, что несмотря все виды горя, которые автору довелось пережить за эти 25 минут, на доске все еще оставалось Би-дерево
Вот к таким священникам надо на службу ходить. Спасибо вам . Очень доходчиво и понятно.
"Обычно у нас деревья растут сверху вниз... .... ... Не говорите биологам!" :D
Иисус лично решил спуститься с небес, что б пояснить за B деревья... Воистину лучший
Пользуюсь вашими видео, каждый раз когда готовлюсь к собеседованиям, спасибо за труд!
Дай Бог Вам здоровья, мне так понравилось ваше объяснение. Вы умничка спасибо Вам большое, Вы очень помогли
Спасибо Вам огромное, Владимир, за такое доходчивое объяснение темы!
Лучшее объяснение этой темы из всех, что я видел. Большое спасибо, очень нравится Ваш канал. Очень качественные объяснения, да и просто приятно смотреть)
Владимир спасибо Вам за ваши лекции по алгоритмам и структурам данных. Очень приятно,в красках, доходчиво преподносите материал! Успехов Вам и развития!)
Мне кажется, что надо назвать твой канал: IT-Иисус. Это будет полностью соответствовать, т.к объясняешь ты, как боженька и очень похож на него)
@canniballissimo
2 жыл бұрын
особенно учитывая, что к середине я понял о чём речь, не смотря предыдущие ролики и будучи вообще не в теме ):
@AZart-infa
Жыл бұрын
И положил он байты с битами по благой последовательности их, и приходили люди, и уверовали онлайн, и святость айтишная воцарилась в душах их, и кодили во славу цифровую до апгрейда их, и никакой баг не поразил их боле, ибо благословенны деяния их.
Добрый день! Благодарю Вас что записали это видео
Спасибо, Володя, за лекцию!
Отличное объяснение! Этим и отличается хороший учитель: простым и доходчивым языком донести сложную тему! Спасибо! Ещё было бы здорово сравнить с B+ деревом, чтобы не путать их. Ведь B+ дерево тоже относится к сбалансированным, но имеет свои нюансы.
Бро это лучшее видео п о структурам данных которое я видел, большое человеческое спасибо
Спасибо за информативное и интересное видео!
Жаль не рассказал про удаление ключа
Лучших объяснений не видел
Идеально!!! Все просто и понятно , спасибо!!
Спасибо, Владимир. Вы наш Павел Флоренский.
Огромное, огромное и еще раз огромное спасибо!!! Очень помогло!!!
Довольно страстное и выразительное изложение. Лайк
Спасибо за лекцию.
классно! наглядно понятно и с примером!
Из всего найденого в ютубе это видео самое доходчивое.
бро, очень круто объяснл, от души спасибо
Очень хорошо объяснено!
Спасибо за отличное видео.
Как чётко.. каждое слово в душу...
Как обычно от нечего делать хотел оставить какой-нибудь язвительный комментарий в интернете, сделав это под видео. Но посмотрел все видео, - действительно классное объяснение, понял многие моменты работы B-деревьев (я не ходил в университет полтора года из-за работы и пропустил эту тему). Очень понравилось, круто, спасибо :)
@DeerRadio
9 жыл бұрын
Я еще диплом пишу, про самообучающуюся модель для 2d real-time игры с видом сверху; Вот, я вообще нейронные сети использовал, но неделю назад посетила идея попробовать сделать обучение и хранение знаний в дереве. Т.е. подается какой-то вектор состояний системы, которые вычисляет бот, на B-дерево знаний; Там по некоторым формулам идет приблизительный поиск подобного вектора в дереве; Если такой есть, то выполняются действия по закону, описанному в найденной ноде. Если нода с таким вектором не найдена, то ожидаем результата действия (т.е., "встретить лицом снаряд танка", игра про танчики :D). Если результат негативный для бота, то в ноде это отражается как-то. Если положительный, то увеличивается. Короче, я еще не реализовывал, т.к. нейронки мучаю Как думаете, стоит ли издеваться над B-деревом таким способом?:) Или нейронные сети реализуют то же самое, но лучше в моей задаче?
@VladimirMozhenkov
9 жыл бұрын
Forged Spirit Ну нейронной сети всё равно где информация хранится. Можно делать и в B-дереве, алгоритму ведь будет всё равно. Тут более, как мне кажется, интересна будет сама функция обучения. Определить хорошо/плохо будет легко, а вот дать достаточное количество вводов, и затем прогнать достаточное количество раз... Хотя если вы делаете оба танка автоматическими и они начинают биться против друг друга, то второй вопрос решается. А по поводу первого, тут наверно проще просто экспериментально посмотреть.
Здравствуйте. Вы очень хоршо и доходчиво объясняите. Мне кажется или на 15 минуте вы "16" подвинули вверх, но 48 так и не добавили? Или я что то не так понял? А так спасибо Вам большое, был бы рад если бы вы продолжали и разобрали к примеру красно-черное дерево=)
@pyramidhead9692
2 жыл бұрын
А вот вопрос кстати очень интересный. Потому что он по идее того должен был поменять местами 23 и 43, так как нода получалась не сортированной.
@user-jn6tc3qe1h
Жыл бұрын
@@pyramidhead9692 48 просто запишется правее 23, так же как записывались 13 и 5 в самом начале.
Мужик, ты очень крут! Спасибо большое!
"не говорите биологам" в голос. однозначно лайк
Отличное видео, спасибо
Спасибо, классное видео!
"Обычно у нас растут деревья сверху вниз"... далее лицо Володи....
Отлично объяснил! Спасибо огромное)
@VladimirMozhenkov
10 жыл бұрын
Очень рад, что помог. Это весьма сложная структура, мне понадобилось очень много времени для выяснения сути происходящего. Обычно всё объясняют математически, и приходится очень долго вникать, чтобы понять весьма простые вещи.
@user-ke1se2sg2n
10 жыл бұрын
Это точно, уж очень бывает перегибают. www.cs.usfca.edu/~galles/visualization/Algorithms.html Тут хорошо интерактивно можно въехать в суть, но блин без понятной теории это тоже тяжело даётся:)
Thanks, Jesus, very informative !
Разжевал, так разжевал! Спасибо тебе мужик!
Так бы в универе преподавали. Спасибо огромное!
Спасибо огромное!!!
Благодарю!
Спасибо! Помогло.
Спасибо, Владимир, все доходчиво и понятно на примере. Про 48 все ясно - оно максимально и роли не играет, нечаянно пропустили. Возник другой вопрос - Вы говорите, что при M=2 дерево будет бинарным. Если не изменяет память, то в бинарном дереве количество потомков НЕ БОЛЕЕ двух, т.е. включая 1. Но ведь это не верно для B-деревьев при M=2? Или я что-то напутал?
Спасибо!
Пожелание - очень хочется понять знания из области аналитической механики. Спасибо!
а где делось число 48?
@user-wb5dh1ps4x
5 жыл бұрын
проебали
шикарно обьяснил
спасибо большое
Спасибо, отец
Благодарю
Когда смотришь видео айти-батюшки 8-летней давности... Без шуток,объяснятешь ты как боженька)
Хорошо объяснил, очень доходчиво! Но, не лишним было бы рассказать и про удаление элементов, доступ к элементам.
1 Так говорит Господь: небо - престол Мой, а земля - подножие ног Моих; где же построите вы дом для Меня, и где место покоя Моего? 2 Ибо все это соделала рука Моя, и все сие было, говорит Господь. А вот на кого Я ПРИЗРЮ: на смиренного и сокрушенного духом и на трепещущего пред словом Моим. 3 Заколающий вола - то же, что убивающий человека; приносящий агнца в жертву - то же, что задушающий пса; приносящий семидал - то же, что приносящий свиную кровь; воскуряющий фимиам - то же, что МОЛЯЩИЙСЯ ИДОЛУ; И КАК ОНИ ИЗБРАЛИ СОБСТВЕННЫЕ СВОИ ПУТИ, И ДУША ИХ НАХОДИТ УДОВОЛЬСТВИЕ В МЕРЗОСТЯХ ИХ, - 4 так и Я употреблю их обольщение и НАВЕДУ НА НИХ УЖАСНОЕ ДЛЯ НИХ: потому что Я звал, и не было отвечающего, говорил, и они не слушали, а ДЕЛАЛИ ЗЛОЕ В ОЧАХ Моих и избирали то, что неугодно Мне. 5 Выслушайте слово Господа, трепещущие пред словом Его: ваши братья, ненавидящие вас и изгоняющие вас за имя Мое, говорят: "пусть явит Себя в славе Господь, и мы посмотрим на веселие ваше". Но ОНИ БУДУТ ПОСТЫЖЕНЫ. (Ис.66:1-5)
А что по поводу удаления из B-дерева?
Спасибо за экскурс по b-деревьям. Но как же удалять элементы из b-деревьев?
@PoletaevRoman
3 жыл бұрын
Если нужно удалить, то горе нам!
@TheSemgold
3 жыл бұрын
Там нужно у правых сыновей красть по ситуации.
Хотелось бы предварительно осветить понятия бинарного дерева и нода, а потом уже переходить к B-деревьям. Излагаете хорошо.
Огонь чувак
Подписался!
Спасибо
Насчет числа 48, это он случайно пропустил :) Просто представьте, что мы провернули все это для числа 15, то есть наша последовательность выглядит так: 8,13,5,0,16,7,23,15, суть от этого не меняется.
Володя, спасибо за объяснение! Скажите пожалуйста, а не могли бы вы объяснить как работают B+ деревья? Благодарю.
@VladimirMozhenkov
8 жыл бұрын
+Eugene Pashkevich С ними не работал, но может узнаю и запишу если будет муза )))
Владимир, напишите в комментарии куда вы 48 вставили!
Снял бы для полноты картины и про Dancing tree
Спасибо завашу работу. У меня один вопрос. Вы говорили про то, что указаталей может быть либо 0, либо 6. Что имело ввиду, так как по факту вы показали иначе. Спасибо!
@gogol-mogol779
4 жыл бұрын
Я это понял иначе. Если у тебя есть блок с 5 значениями, то на следующем уровне у тебя будет либо 0 нод либо 6
При разрыве берётся центральное или среднее? Просто если есть 2 ключа, то и центрального там не будет
Гений!
Вы говорите что можно сбалансировать Btree дерево с М = 2. Но ведь для этого придется добавлять сразу по два значения в дерево. Иначе оно не будет сбалансированным. Другими словами - Btree дерево можно полностью сбалансировать только если в нем нечетное кол-во значений, я правильно понимаю?
@VladimirMozhenkov
8 жыл бұрын
+Yauheni Neshyn Нет, оно балансируется обязательно всегда, с любым количеством значений. Вы просто сбросите одно значение из корня вниз.
Когда мы 0 добавляли, то получается, что мы как бы не крайние элементы вниз убирали, а наоборот центральный наверх, судя по дальнейшей логике добавления.
Где эти деревья интересно используются
Пожалуйста объясните как так получилось что если м=4 на левой стороне в самом нижнем уровне оказалось 4 нод а не 3? Ведь по правилам В деревьев должно быть не больше или равно м-1?
Что насчет удаления? Будет видео?
а как смещаются элементы при m=5?
А куда делось число 48?
Подскажите, пожалуйста, может кто-либо знает: "Как найти элемент В-дерева, предшествующий данному ключу?"
Почитав несколько ресурсов про b-tree, я ни где не встречал такого обозначения как "M" (уровень). Везде (например, wiki) фигурирует некий параметр "t", от которого зависит количество ключей в ноде (при этом, в корне и в узлах, разные ограничения на количество ключей). Поясните, пожалуйста, существует ли какая-то зависимость между t и M?
@VladimirMozhenkov
8 жыл бұрын
+Alexander Kuleshov Может это из-за того, что я постоянно на английском всё читаю. В англоязычной википедии есть m - максимальное количество дочерних узлов, но они её сделали мальнькой. en.wikipedia.org/wiki/B-tree#Definition Не стоит заострять внимание на том, какая буква используется. Можно было взять что-то из греческого, еврита, арабского, да даже кириллицы, смотря на русскую википедию мне кажется тут о том-же самом говорят. Сколько может быть "ссылок" на дочерние элементы у данного.
@MrGOODliker
7 жыл бұрын
Дело в том, что и в англоязычной и в русскоязычной википедии, да и в книгах с теорией о B-деревьях говорится, что если уровень дерева M, то количество ключей в узле может быть от 1 до 2*М-1. Из вашего видео ясно видно, что количество ключей в узле не превышает М-1. Тут получается расхождение, совсем разные деревья получатся... Так где же правда?:)
@ne_olesyna
4 жыл бұрын
@@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 это количество значений и указателей в одном узле.
Ребят, не очень понял на 8:40 - 9:00 Почему максимум может быть 4 дочерних ноды и максимум 3 значения?
@trell_7842
4 жыл бұрын
Как я понял, M=4 означает, что 4 указателя, от одного указателя 1 дочерна , поэтому и 4 дочерних. А в 4 указателя можно вписать только 3 значения, потому-что нужно, чтобы указатели окружали их с обоих сторон. Возможно уже поздно, но всё же
Я не понял вот что. Индексы в оракле - сбалансированные деревья. Но какой у них тогда уровень?
пушка
Вообще ничего не понял. Как так получается, что на верхнем уровне 3 значения, а на нижнем больше 4 нод, если сами говорили про количество значений+ 1?
А почему вы добавили 7 именно на конец левого узла, а не в начало правого, потому что 7 ближе к 5-и чем к 13-и?
@user-ij3hx7qp4i
3 жыл бұрын
Потому что в правом узле хранились значения не меньше 8
А все-таки, куда у вас делось число 48?
С удалением записи из узла никак разобраться не получается. Не пойму, как должна происходить балансировка
а 48 почему-то и не вставили
забыли сказать что фактор для нижних уровней должен быть 2t-1, чтобы при разбиении в случае заполнения разбивалось на два равных ноды, и оставался один элемент для переноса вверх
Прошу пояснений 4.10 говорим количество нод 0 или разрядность дерева. В дальнейшем слышу может быть меньше. Противоречие
Если кто не знал, узлы он называет нодами(лично я не слышал про такое), иб тоже кто то затупил
а как би-дерево может быть бинарным, если в нем 2 элемента?
Не знал, что Джаред Лето... разбирается в теории алгоритмов.
Хм... Всё ещё не понял что это за деревья такие, как с ними работать и как это работает в БД
Раз уж от 63..inf в последнем диапазоне, то тогда -inf..2 в первом диапазоне =)
@VladimirMozhenkov
10 жыл бұрын
Ну я выбирал неотрицательные числа у себя в голове... вот и отсутствие отрицательной бесконечности. Но наверно с чисто технической стороны вы совершенно правы! q;-)))=
Борода потерял 48 где-то по дороге
За всем этим весельем потеряли 48, куда его добавили то
не рассказанная глава Евангелие, пишники ставьте лайк, если вы от рамона
@DantesioUD
3 жыл бұрын
Воистину, едины в Залупиносе....
какой ж ты волосючий:D
Забыл 48
Раздражает постоянное перебирание фломастеров + это тормозит. Пожалуйста, используйте 1 цвет или хотя бы колпачок не закрывайте
@Bguiysigziggzog
2 жыл бұрын
во наглая
это беларуский акцент?
@VladimirMozhenkov
2 жыл бұрын
У меня? На вряд-ли. Я там никогда не был. Но мне говорили люди, что моя буква "ч" очень похожа на беларусскую.
48 так и не добавили
Ой-вэй, еврейское счастье, а как насчёт наглядного практического применения? Когда наглядно обыгрывается ситуация применения