Jaka jest najbardziej wydajna technika indeksowania danych

10

Jak wszyscy wiemy, istnieją pewne techniki indeksowania danych, które są używane przez dobrze znane aplikacje indeksujące, takie jak Lucene (dla java) lub Lucene.NET (dla .NET), MurMurHash, B + Tree itp. Dla obiektu bez Sql / Object Oriented Database (którą próbuję napisać / grać trochę w C #), jaką technikę sugerujesz?

Czytałem o MurMurhash-2, a zwłaszcza komentarze v3 mówią, że Murmur jest bardzo szybki. Również Lucene.Net ma na ten temat dobre komentarze. Ale co z ich śladami pamięci w ogóle? Czy jest jakieś wydajne rozwiązanie, które zużywa mniej miejsca (i oczywiście jeśli preferowane jest szybsze) niż Lucene lub Murmur? Czy powinienem napisać specjalną strukturę indeksu, aby uzyskać najlepsze wyniki?

Jeśli spróbuję napisać własną, to czy istnieje jakakolwiek akceptowana skala dobrego indeksowania, coś w rodzaju 1% węzła danych lub 5% węzła danych? Każda przydatna wskazówka zostanie doceniona.

sihirbazzz
źródło

Odpowiedzi:

10

Myślę, że pomieszałeś niektóre rzeczy w swoim pytaniu. Lucene (nic nie wiem o Lucene, NET, ale przypuszczam, że jest tak samo) to biblioteka używana do analizy, dzielenia na tokeny i przechowywania dokumentów w celu późniejszego ich wyszukania i odzyskania. Lucene ma dość stary, ale skuteczny model, wykorzystuje odwrócone drzewa do wyszukiwania i wyszukiwania dokumentów. Bez dalszych szczegółów wszystkie dokumenty są podzielone na tokeny (warunki), a dla każdego terminu jest utrzymywana struktura danych, która przechowuje wszystkie dokumenty zawierające dany termin. Jako strukturę danych można zastosować BTree, tablicę skrótów, aw najnowszych ważnych wersjach można nawet podłączyć własne struktury danych.

BTree ( więcej szczegółów na stronie Wikipedii ) jest rodzajem struktury danych drzewa, która jest odpowiednia do pracy z dużymi fragmentami danych i często służy do przechowywania uporządkowanych struktur drzewa na dysku. W przypadku pamięci inne drzewa działają lepiej.

Murmur hash ( więcej szczegółów na stronie Wikipedii ), to rodzina funkcji hash używanych w tabeli skrótów. Wdrożenie tabeli skrótów nie jest ważne, może to być standardowa implementacja łańcuchowa lub bardziej zaawansowany schemat adresowania otwartych skrótów. Chodzi o to, że tabele skrótów pozwalają szybko uzyskać klucz z nieuporządkowanego zestawu kluczy i mogą odpowiadać na zadania takie jak: czy ten klucz jest częścią tego zestawu kluczy? jaka jest wartość związana z tym kluczem?

Teraz wróć do głównego problemu. Masz jedną bibliotekę (Lucene), a do struktur danych obie struktury danych są używane w Lucene. Teraz widzisz, że na te pytania nie można odpowiedzieć, ponieważ nie są one porównywalne.

Jednak w odniesieniu do twojego śladu i wydajności część pytania. Przede wszystkim musisz wiedzieć, jakie operacje musisz wdrożyć.

Czy potrzebujesz tylko wartości dla klucza, czy też musisz znaleźć wszystkie elementy w zakresie? Innymi słowy, potrzebujesz zamówienia czy nie? Jeśli tak, to drzewo może pomóc. Jeśli tego nie zrobisz, zamiast tego można użyć szybszej tabeli skrótów.

Czy masz dużo danych, które nie pasują do pamięci? Jeśli tak, pomogłoby rozwiązanie oparte na dysku (jak BTree). Jeśli twoje dane mieszczą się w pamięci, użyj najszybszego rozwiązania w pamięci i użyj dysku tylko jako magazynu (o innej strukturze, o wiele prostszej).

rapaio
źródło
Dziękuję bardzo Rapaio :) Punkty, które mi dałeś, są bardzo przydatne i uzyskują coś jaśniejszego .. Ponieważ jestem programistą .NET i ciekawy na zwykłym C (zaczynam się uczyć) i nowy, szybki, niezawodny, skalowalny ancd oczywiście w pełni kontrolowane - w krótkim okresie: bardzo podekscytowane - techniki. Więc muszę się dużo nauczyć. Aby się nauczyć, staram się czytać tak wiele dokumentów, ale jak można się domyślić, jestem na linii startu .. Nie wiedziałem, że BTree ma zalety na dysku (w świecie .Net, tak wielu pisarzy wyjaśnia to tak: Hierarchiczna struktura danych, jak Linked-List .. Nie więcej!)
Jeszcze
A jeśli mi na to pozwolisz, dopóki nie znajdziesz wyższej jakości wyjaśnienia / odpowiedzi niż twoje, chcę zaakceptować to jako odpowiedź. A BTW, Lucene.NET to implementacja Lucene w Javie
sihirbazzz