Czerwone czarne drzewo kontra drzewo B

Question

Czerwone czarne drzewo kontra drzewo B

Mam projekt, w którym muszę osiągnąć szybkie wyszukiwanie, wstawianie i usuwanie operacji na danych od megabajtów do terabajtów. Ostatnio studiowałem struktury danych i analizowałem je. Mówiąc konkretnie, chcę przedstawić 3 przypadki i zadawać pytania na ten temat:

Dane są znacznie więcej niż to, co pamięć może obsłużyć (przykładowe zakresy w 10-15 terabajtów) za jednym zamachem. W takim przypadku zapisałbym strukturę danych na dysku.
Dane są stosunkowo mniej w porównaniu do pamięci systemu, a tym samym może być przechowywany i obsługiwany w samej pamięci dla szybkości.
Dane to więcej niż wolna pamięć i załóżmy, że jest mniejsza niż rozmiar możliwego sąsiedniego fragmentu danych w pliku stronicowania. w ten sposób przechowuję strukturę danych w pliku na dysku i wykonuję mapowanie pamięci pliku.

Wnioski, które wyciągnąłem są następujące:

W przypadku 1, powinienem użyć drzewa B dla szybszego dostępu, ponieważ oszczędza na lag wytwarzanym przez obrót dysku

W przypadku 2 powinienem użyć czerwonego czarnego drzewa dla szybszego dostępu, ponieważ dane są w pamięci i nie. elementy potrzebne do skanowania w gorszym przypadku byłyby mniejsze niż jeden, który muszę zrobić, jeśli używam drzew B

W przypadku 3 wątpię, w tym przypadku Plik strony jest na dysku używa natywnego OS I / O do operowania na plikach, więc czy B Tree powinno być lepszą opcją czy czerwono-czarnym drzewem?

Chcę wiedzieć, gdzie powyższe trzy wnioski idą dobrze, a gdzie źle i jak Mogę poprawa wydajności w trzech oddzielnych przypadkach.

Używam języka C++, z czerwonym czarnym drzewem i drzewem B, które zaprojektowałem od podstaw. Używam Biblioteki Boost do mapowania plików.

Update 1:: Was reading through this post in stackoverflow. Mam kilka naprawdę dobrych spostrzeżeń, które sprawiają, że czuję, że rodzaj porównań zrobiłem w przypadkach może być wadliwy. Link został zamieszczony w najczęściej-głosowanych-na-odpowiedź http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

33

large-data data-structures b-tree red-black-tree file-mapping

Author: Community, 2011-06-19

Source

2 answers

Aby zrozumieć różnicę między nimi, przeczytaj poniżej 2 punkty:

1) "czerwono-czarne drzewo "jest" samobalansującym "" binarnym drzewem wyszukiwania", z każdym węzłem oznaczonym kolorem (czerwonym lub czarnym) i zdefiniowanymi na nim dodatkowymi operacjami utrzymania "równowagi"

2) Wszystkie "czerwono-czarne drzewo" S są "binarnym drzewem wyszukiwania" s, ale wszystkie "binarne drzewo wyszukiwania" s nie są "czerwono-czarnym drzewem" s

0

Author: Muhammad Noman,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-03-09 18:28:20

score 10 · Accepted Answer

Czerwone / czarne drzewo jest mniej więcej równoznaczne z drzewem 2-3-4, które jest tylko rodzajem drzewa B. W najgorszym przypadku wydajność jest identyczna, pod warunkiem, że wykonasz binarne wyszukiwanie wartości węzła B-tree.

Oczywistą wadą drzewa B jest marnowanie przestrzeni, ale w zależności od używanego języka / alokatora pamięci, może się okazać, że drzewo 2-3-4 zużywa mniej przestrzeni niż średnio czerwono-czarne drzewo. Na przykład w 32-bitowej Javie na obiekt przypada około 8-bajtowy narzut. (To również zależy dużo na alokatorze; IIRC phkmalloc zaokrągla małe alokacje do wielkości mocy 2.)

Aby odpowiedzieć na twoje pytania,

opóźnienie dysku jest mniej więcej równomiernie podzielone między czas poszukiwania i oczekiwanie na obrót dysku.
nie musi być sąsiadujący w pliku strony; musi być tylko sąsiadujący w wirtualnej przestrzeni adresowej procesu. Dla zdrowych systemów operacyjnych jest to również prawie identyczne z przypadkiem 1, chyba że Twoje dane są na tyle małe, że w większości mieszczą się w pamięci, a narzut memcpy jest znaczący.

Dla uproszczenia, wybrałbym drzewo B i uruchomił kilka benchmarków na różnych rozmiarach węzłów.