Комментарии 13
Спасибо! Отличное и очень простое объяснение не очень простых вещей
На мой взгляд, одно из самых больших достоинств B-дерева — это то, что оно спроектировано специально для обработки больших объёмов данных на реальном оборудовании. Вероятно, именно благодаря этому B-дерево так долго популярно.
Спасибо, хорошее объяснение, простое и понятное. Вот только так и не раскрыт вопрос - а что с современными SSD? Они ведь вроде бы вполне быстро обеспечивают произвольный доступ, есть ли смысл с ними заморачиваться такими структурами?
Думаю да, есть смысл в использовании b+ деревьев и на современных устройствах хранения. Ведь flash память тоже работает по странично, хотя и имеет побайтовый доступ. Но побайтовый так же медленнее, потому что нужно постоянно передавать адрес и прочие сигналы, а постранично задаётся короткий номер страницы и дальше только принимать данные.
даже произвольный доступ к оперативной памяти будет медленнее чем последовательный из-за организации кешей процессора. Так что все еще будет оптимальнее использовать специальные структуры данных
Они ведь вроде бы вполне быстро обеспечивают произвольный доступ, есть ли смысл с ними заморачиваться такими структурами?
С ними - ещё более:)
На HDD дискрет перезаписи - 512 байт на классических, 4KB на многих новых (даже если они рапортуют логический размер блока всё те же 512 байт). А вот на SSD минимальный перезаписываемый объём может быть, например, 128KB. Умный контроллер набивает такую порцию многими блоками и обновляет вслед карту распределения, но чем меньше его таким грузить, тем лучше. Поэтому большая страница тут полезнее.
Хотя, 128KB для страницы B-дерева это многовато. Для таких применений придумали Log-structured merge tree.
Статья отличная! Спасибо автору:)
Если кто-то не понял сразу (как я) картинку про представление двоичного дерева в памяти, то вот пояснение:
В последнее время люблю читать про всякие интересные структуры данных...
Я тут подумал: если смотреть с точки зрения ЯПов, а не баз данных, то у такого способа балансировки будет небольшой недостаток в виде того, что она нестабильная (перемещает данные из одного участка памяти в другой).
А так, про кеше-дружелюную реализацию списка уже читал, а вот и аналог для дерева, классно))
Теоретически, использование двоичного дерева поиска для выполнения запросов вполне работает. Его временная сложность (при поиске) равна O(logn), как и у B-дерева.
У них как минимум разная асимптотика. Поиск в BST линия, если дерево вырожденное. Самобалансирующиеся деревья гарантируют поиск за логарифм
Почему B-деревья быстрые?