Блог

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

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

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

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

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

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