Как стать автором
Обновить

Комментарии 13

Спасибо! Отличное и очень простое объяснение не очень простых вещей

НЛО прилетело и опубликовало эту надпись здесь

На мой взгляд, одно из самых больших достоинств B-дерева — это то, что оно спроектировано специально для обработки больших объёмов данных на реальном оборудовании. Вероятно, именно благодаря этому B-дерево так долго популярно.

Спасибо, хорошее объяснение, простое и понятное. Вот только так и не раскрыт вопрос - а что с современными SSD? Они ведь вроде бы вполне быстро обеспечивают произвольный доступ, есть ли смысл с ними заморачиваться такими структурами?

Думаю да, есть смысл в использовании b+ деревьев и на современных устройствах хранения. Ведь flash память тоже работает по странично, хотя и имеет побайтовый доступ. Но побайтовый так же медленнее, потому что нужно постоянно передавать адрес и прочие сигналы, а постранично задаётся короткий номер страницы и дальше только принимать данные.

Ясно, спасибо.

Да нифига подобного, nand flash имеет только постраничный доступ. И более того, читать всю страницу надо просто потому, что там вместе с данными избыточные коды исправления ошибок.

Та память что ставится в SSD в основной массе да, только постраничный доступ, но вот у меня лежит несколько штук W25N01G, она и побайтово умеет читать, но это SPI чипы.

НЛО прилетело и опубликовало эту надпись здесь

даже произвольный доступ к оперативной памяти будет медленнее чем последовательный из-за организации кешей процессора. Так что все еще будет оптимальнее использовать специальные структуры данных

Они ведь вроде бы вполне быстро обеспечивают произвольный доступ, есть ли смысл с ними заморачиваться такими структурами?

С ними - ещё более:)

На HDD дискрет перезаписи - 512 байт на классических, 4KB на многих новых (даже если они рапортуют логический размер блока всё те же 512 байт). А вот на SSD минимальный перезаписываемый объём может быть, например, 128KB. Умный контроллер набивает такую порцию многими блоками и обновляет вслед карту распределения, но чем меньше его таким грузить, тем лучше. Поэтому большая страница тут полезнее.

Хотя, 128KB для страницы B-дерева это многовато. Для таких применений придумали Log-structured merge tree.

Статья отличная! Спасибо автору:)

Если кто-то не понял сразу (как я) картинку про представление двоичного дерева в памяти, то вот пояснение:

В последнее время люблю читать про всякие интересные структуры данных...

Я тут подумал: если смотреть с точки зрения ЯПов, а не баз данных, то у такого способа балансировки будет небольшой недостаток в виде того, что она нестабильная (перемещает данные из одного участка памяти в другой).

А так, про кеше-дружелюную реализацию списка уже читал, а вот и аналог для дерева, классно))

Теоретически, использование двоичного дерева поиска для выполнения запросов вполне работает. Его временная сложность (при поиске) равна O(logn), как и у B-дерева

У них как минимум разная асимптотика. Поиск в BST линия, если дерево вырожденное. Самобалансирующиеся деревья гарантируют поиск за логарифм

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории