Каковы недостатки красных черных деревьев?

Question

Из всего, что я читал о красно-черных деревьях, кажется, что они - лучшая структура данных для хранения данных.

Я пытаюсь создать базу данных, и мне интересно, только в аспекте реализации Red - Black деревьев, где я должен быть более осторожным и что я не должен делать.

Действительно ли красно-черные действительно идеальны?

Answer 1

Зависит от того, как вам нужно запрашивать и обновлять данные.Если, например, вам не нужны упорядоченные данные, хеш-карты, вероятно, лучше, так как они имеют (ожидаемое) постоянное время поиска / вставки вместо логарифмического.Даже если вам нужны упорядоченные данные, красные / черные деревья могут быть не идеальны - в частности, если вы не реализуете базу данных на диске.В дисковых операциях ввода-вывода поиск обходится дороже по сравнению с последовательным чтением блоков, поэтому цель состоит в том, чтобы минимизировать количество обращений к диску.В таких случаях B-деревья (или B + -дерево, или B * -дерево) лучше - все они предназначены для быстрой работы при хранении на дисках.

Answer 2

Красно-черные деревья далеко не идеальны для ВСЕГО доступа к данным. У них есть свое место, но во многих случаях лучше использовать другие методы, такие как хэшированные карты и простые старые списки.

Одним заметным недостатком красно-черных деревьев во многих случаях является то, что это двоичное дерево, и, следовательно, поиски - это O (lg (n)), где в качестве хеш-таблиц есть поиск O (1).