Pull to refresh

Comments 32

Классный симулятор. Завис на нем немного
Спасибо!
Блин. Вроде не у всех Фул ХД экраны. Не удобно скроллить вниз, нажимать инсерт, потом скроллить вверх, чтобы позырить анимашку
А вы присмотритесь к урлу.
Одно из моих любимых деревьев
Простите, сорвалось. Хотел написать «как прекрасно звучит» :)
А зачем топик закрытый? Многие не увидят.
Очень быстро и походя описана процедура выборки. Наверное, для людей, которые «в теме», это понятно, но при чтении со стороны (для общего развития) преимущества перечислены быстро, а вот недостатки разбираются тщательно.
Попробуйте вставить сортированные данные и поймете, зачем есть RB-tree.
Пара замечаний:

1. O(log_2(N)) = O(log_t(N)), разница лишь в константе. С точки зрения математика-чистоплюя, никакой разницы в смысле скорости поиска между красно-черным и B-деревом нету.
2. Кроме того, математик-чистоплюй тут же поинтересуется, каким способом производится поиск нужного пути ветвления и, узнав что для того чтоб понять, к какому потомку идти дальше, нужно прошерудить 1000 ключей узла, поморщится и спросит, а если разница хотя бы даже в константе.

А программист, который тоже математик, но которого константа волнует, должен знать, что:
a) время поиска внутри узла совершенно никого не интересует, потому что оно в миллион раз меньше времени считывания блока с диска
б) данные с классического HDD считываются поблочно
в) именно размером блока определяется то, сколько в нём будет ключей, а не тем, сколько у нас там оперативной памяти. Размер буфера RAM влияет конечно же на то, сколько узлов диска в него поместится, но не размер самого узла

Про нагрузку на сервер и время ожидания совсем уж как-то зря. Производительность СУБД зависит конечно от эффективной структуры данных для индекса, но намного больше она зависит от совершенно других вещей
Спасибо за замечания
Скажу пару слов в ответ:
Про математика-чистоплюя — я безусловно нигде и не хотел сказать, что B-tree работает быстрее, чем тоже красно-черное или другое. Я везде подчеркивал лишь то, что оно не уступает им по скорости (здесь имеется ввиду скорость именно вычислений, а не считываний с диска)

Про считывание с диска блоками — безусловно это так. Я действительно допустил небольшую неточность. Надо сказать, что размер узла обычно соответствует дисковой странице, а t (минимальная степень) выбирается в зависимости от размера одного ключа относительно размера всей страницы

Про СУБД — не знаю, если честно. Нам рассказывали, что это одна из важных частей в реализации базы данных. Да и я сам пробовал, что без индексов всё работает гораздо медленнее. Поэтому считаю нужным, чтобы люди знали это
Конечно одна из важных и конечно при наличии индексов что-то будет работать быстрее, но кое-что может стать и медленнее, в зависимости от степени тупизны оптимизатора запросов в СУБД.

Вот этот запрос наверняка выиграет от наличия индекса для id:

SELECT *FROM T WHERE id=100

а вот этот от неуместного использования индекса по столбцам foo может и проиграть:

SELECT * FROM A JOIN B ON (A.foo > B.foo)


Ааа. Ясно, что имеется ввиду. Я лишь имел ввиду, что благодаря индексам можно выиграть во времени — и причем прилично. Понятно, что не всегда — иначе это была бы какая-то панацея от всех бед
Если повернуть дерево на 90 градусов — получится «дерево, растущее корнем вбок» :-)
UFO landed and left these words here
односвязный список, как тема курсовой. мдя…
UFO landed and left these words here
UFO landed and left these words here
> Важно здесь, что дисковых операций мы совершаем всего лишь O(logt n)!
Это ведь не факториал?
Первый раз узнал о таких деревьях в видео с конференции с Highload++ от Аксенова. Очень интересно и познавательно, он про индексирование в БД рассказывает. Кому интересно, можете посмотреть на smotri.com (вбиваем в поиск «Highload++»)
А по подробней можно? там очень большой ркзультат по этому ключевому слову, прямой ссылки нет?
Делал как-то хранилище террабайтного размера (всмысле размером n-терробайт) основанное на RB деревьях (кстати RB дерево можно рассматривать как B-дерево с кол-вом потомков = 4).

Занятное было дело надо сказать :) но на стандартных для 5 летней давности машинах добавление записей происходило со скоростью около 2 миллионов ключей в секунду… Но к сожалению проект, для которого я делал это хранилище (новая поисковая система) приказал долго жить ;) ;) ;)
Ну раз вставка и удаление такие долгие, то нет ли смысла сразу вырастить большое дерево с запасом, а вместо удаления элементов просто помечать их как нулевые?
Растить большое дерево с запасом смысла наверное не имеет, потому что «запас» не будет использоваться. Вставка на самом деле не так уж и дорога, ибо расщепление узлов на уровне выше чем над-листьями врядли будет происходить очень уж часто.

Ставить надгробие вместо настоящего удаления смысл имеет.

Желающим — дополнительная литература про индексные структуры во внешней памяти.

На русском в онлайн: citforum.ru/programming/theory/sorting/sorting2.shtml#5
На русском в офлайн: «Системы баз данных: полный курс» авторства Ульмана, Уидома и Гарсиа-Молина
Для эстетов та же книга на отличном английском называется «Database Systems: The Complete book», и у неё есть не менее интересное первое издание «Database System Implementation».
скажите пожалуйста, а где хранятся значения для ключей? допустим если мы делаем словарь на основе Б-дерева
Only those users with full accounts are able to leave comments. Log in, please.