Comments 32
Одно из моих любимых деревьев. Вот тут есть еще симулятор его, кто хочет поиграться: slady.net/java/bt/view.php?w=1024&h=768
(надеюсь не упадет)
(надеюсь не упадет)
А зачем топик закрытый? Многие не увидят.
Очень быстро и походя описана процедура выборки. Наверное, для людей, которые «в теме», это понятно, но при чтении со стороны (для общего развития) преимущества перечислены быстро, а вот недостатки разбираются тщательно.
Пример исходника на Delphi кому интересно www.delphisources.ru/forum/showthread.php?t=15106
Попробуйте вставить сортированные данные и поймете, зачем есть RB-tree.
Пара замечаний:
1. O(log_2(N)) = O(log_t(N)), разница лишь в константе. С точки зрения математика-чистоплюя, никакой разницы в смысле скорости поиска между красно-черным и B-деревом нету.
2. Кроме того, математик-чистоплюй тут же поинтересуется, каким способом производится поиск нужного пути ветвления и, узнав что для того чтоб понять, к какому потомку идти дальше, нужно прошерудить 1000 ключей узла, поморщится и спросит, а если разница хотя бы даже в константе.
А программист, который тоже математик, но которого константа волнует, должен знать, что:
a) время поиска внутри узла совершенно никого не интересует, потому что оно в миллион раз меньше времени считывания блока с диска
б) данные с классического HDD считываются поблочно
в) именно размером блока определяется то, сколько в нём будет ключей, а не тем, сколько у нас там оперативной памяти. Размер буфера RAM влияет конечно же на то, сколько узлов диска в него поместится, но не размер самого узла
Про нагрузку на сервер и время ожидания совсем уж как-то зря. Производительность СУБД зависит конечно от эффективной структуры данных для индекса, но намного больше она зависит от совершенно других вещей
1. O(log_2(N)) = O(log_t(N)), разница лишь в константе. С точки зрения математика-чистоплюя, никакой разницы в смысле скорости поиска между красно-черным и B-деревом нету.
2. Кроме того, математик-чистоплюй тут же поинтересуется, каким способом производится поиск нужного пути ветвления и, узнав что для того чтоб понять, к какому потомку идти дальше, нужно прошерудить 1000 ключей узла, поморщится и спросит, а если разница хотя бы даже в константе.
А программист, который тоже математик, но которого константа волнует, должен знать, что:
a) время поиска внутри узла совершенно никого не интересует, потому что оно в миллион раз меньше времени считывания блока с диска
б) данные с классического HDD считываются поблочно
в) именно размером блока определяется то, сколько в нём будет ключей, а не тем, сколько у нас там оперативной памяти. Размер буфера RAM влияет конечно же на то, сколько узлов диска в него поместится, но не размер самого узла
Про нагрузку на сервер и время ожидания совсем уж как-то зря. Производительность СУБД зависит конечно от эффективной структуры данных для индекса, но намного больше она зависит от совершенно других вещей
Спасибо за замечания
Скажу пару слов в ответ:
Про математика-чистоплюя — я безусловно нигде и не хотел сказать, что B-tree работает быстрее, чем тоже красно-черное или другое. Я везде подчеркивал лишь то, что оно не уступает им по скорости (здесь имеется ввиду скорость именно вычислений, а не считываний с диска)
Про считывание с диска блоками — безусловно это так. Я действительно допустил небольшую неточность. Надо сказать, что размер узла обычно соответствует дисковой странице, а t (минимальная степень) выбирается в зависимости от размера одного ключа относительно размера всей страницы
Про СУБД — не знаю, если честно. Нам рассказывали, что это одна из важных частей в реализации базы данных. Да и я сам пробовал, что без индексов всё работает гораздо медленнее. Поэтому считаю нужным, чтобы люди знали это
Скажу пару слов в ответ:
Про математика-чистоплюя — я безусловно нигде и не хотел сказать, что B-tree работает быстрее, чем тоже красно-черное или другое. Я везде подчеркивал лишь то, что оно не уступает им по скорости (здесь имеется ввиду скорость именно вычислений, а не считываний с диска)
Про считывание с диска блоками — безусловно это так. Я действительно допустил небольшую неточность. Надо сказать, что размер узла обычно соответствует дисковой странице, а t (минимальная степень) выбирается в зависимости от размера одного ключа относительно размера всей страницы
Про СУБД — не знаю, если честно. Нам рассказывали, что это одна из важных частей в реализации базы данных. Да и я сам пробовал, что без индексов всё работает гораздо медленнее. Поэтому считаю нужным, чтобы люди знали это
Конечно одна из важных и конечно при наличии индексов что-то будет работать быстрее, но кое-что может стать и медленнее, в зависимости от степени тупизны оптимизатора запросов в СУБД.
Вот этот запрос наверняка выиграет от наличия индекса для id:
а вот этот от неуместного использования индекса по столбцам foo может и проиграть:
Вот этот запрос наверняка выиграет от наличия индекса для id:
SELECT *FROM T WHERE id=100
а вот этот от неуместного использования индекса по столбцам foo может и проиграть:
SELECT * FROM A JOIN B ON (A.foo > B.foo)
Если повернуть дерево на 90 градусов — получится «дерево, растущее корнем вбок» :-)
UFO just landed and posted this here
> Важно здесь, что дисковых операций мы совершаем всего лишь O(logt n)!
Это ведь не факториал?
Это ведь не факториал?
Первый раз узнал о таких деревьях в видео с конференции с Highload++ от Аксенова. Очень интересно и познавательно, он про индексирование в БД рассказывает. Кому интересно, можете посмотреть на smotri.com (вбиваем в поиск «Highload++»)
Делал как-то хранилище террабайтного размера (всмысле размером n-терробайт) основанное на RB деревьях (кстати RB дерево можно рассматривать как B-дерево с кол-вом потомков = 4).
Занятное было дело надо сказать :) но на стандартных для 5 летней давности машинах добавление записей происходило со скоростью около 2 миллионов ключей в секунду… Но к сожалению проект, для которого я делал это хранилище (новая поисковая система) приказал долго жить ;) ;) ;)
Занятное было дело надо сказать :) но на стандартных для 5 летней давности машинах добавление записей происходило со скоростью около 2 миллионов ключей в секунду… Но к сожалению проект, для которого я делал это хранилище (новая поисковая система) приказал долго жить ;) ;) ;)
Ну раз вставка и удаление такие долгие, то нет ли смысла сразу вырастить большое дерево с запасом, а вместо удаления элементов просто помечать их как нулевые?
Желающим — дополнительная литература про индексные структуры во внешней памяти.
На русском в онлайн: citforum.ru/programming/theory/sorting/sorting2.shtml#5
На русском в офлайн: «Системы баз данных: полный курс» авторства Ульмана, Уидома и Гарсиа-Молина
Для эстетов та же книга на отличном английском называется «Database Systems: The Complete book», и у неё есть не менее интересное первое издание «Database System Implementation».
На русском в онлайн: citforum.ru/programming/theory/sorting/sorting2.shtml#5
На русском в офлайн: «Системы баз данных: полный курс» авторства Ульмана, Уидома и Гарсиа-Молина
Для эстетов та же книга на отличном английском называется «Database Systems: The Complete book», и у неё есть не менее интересное первое издание «Database System Implementation».
картинки бы перезалить…
скажите пожалуйста, а где хранятся значения для ключей? допустим если мы делаем словарь на основе Б-дерева
Sign up to leave a comment.
B-tree