btree z partal keys

Mam dużo nazw, tekstów do zapisania, które się często powtarzają,
więc wymyśliłem sposób na to: btree z częściowymi kluczami.

Pomysł polega na tym, że tworzę indeks b-drzewa, w którym zamiast całych nazw będą tylko 2 pierwsze znaki,
a wtedy wystarczy tylko jeden poziom do zapisania milionów pozycji.

Na początku tworzę jeden klucz w indeksie: FFFF, czyli maksymalny (2 znaki zawsze mieszczą się: 0000..FFFF)
Potem będzie to się rozrastać zwyczajnie, poprzez połowienie stron - liści,
dojdzie nowy klucz do indeksu, np.: 'KB', itd.

Każda strona z danymi niech ma rozmiar 4KB, albo 16KB, wtedy zmieści się tam 100-500 tekstów: 4000/20 = 200

Oszacowanie pojemności:
indeks o rozmiarze 16KB pomieści 16000/ 8 = 2000, kluczy częściowych (2B + 4 na adres strony = 6),

zatem biorąc średnio 20 znaków na tekst do zapisania, w sumie taka prymitywna baza pomieści:
2000 x 200 = 400 000;

co powinno wystarczyć do zapisu dowolnego słownika.

Pytanie: są takie bazy znane - używane?
Zwykle słyszę że B-drzewa rozrastają się do 8 poziomów i głębiej, co prowadzi do wielu problemów i komplikacji kodu.

Milion tal temu używaliśmy w firmie C-tree firmy Faircom.
Kompilowało się (j.C) w pewnym stopniu elastycznie, być może był nawet wybór implementacji drzew (nie pamiętam jakie)
generalnie TO BYŁO BARDZO NISKOPOZIOMOWE, fajne, szybkie, wydajne co do RAM, na owe czasy nam pasjonatom się podobało.
(dziś uważam, że zbyt ku technice, za mało ku wiedzy dziedzinowej, wydaniom może nie tak dopracowanych, ale szybciej itd).

W tych czasach szukasz bazy tak niskopoziomowej?

Co jeśli wszystkie nazwy będą się zaczynać na "KB"? Drzewo zdegraduje się do jednego liścia?

B-tree to raczej drzewo oparte na porządku liniowym, a nie na analizie klucza. Drzewo oparte na analizie klucza to np https://en.wikipedia.org/wiki/Radix_tree

Wibowit napisał(a):

Co jeśli wszystkie nazwy będą się zaczynać na "KB"? Drzewo zdegraduje się do jednego liścia?

Na tym polega tu problem.

Można użyć więcej znaków w indeksie, np. 4, ale wtedy znowu się przepełni.

Zatem należy zapisywać kontynuacje, to znaczy po przepełnieniu tworzymy klucz obok, jak kontynuację: 3 i 4 znak.
KB + kontynuacja = 4 znaki.

Użyj jakiegoś gotowca, np https://en.wikipedia.org/wiki/Redis Ma listy, zbiory, mapy i inne dodatki.

Faktycznie coś mi się uroiło,
być może miałoby to sens dla dużych, ogromnych danych: w setkach milionów, ale nie dla miliona.

wywalić temat do kosza.

To co opisałeś brzmi jak Trie a nie jak B-tree, ale mimo wszystko pytanie czy serio masz tyle danych żeby trzeba było tak kombinować...

Są znane B-derzewa z partial keys, kiedyś coś na ten temat czytałem, można poszukać w sieci.

Natomiast Trie to chyba te drzewa odwrócone, w których się po literce idzie;
być może dobra metoda do kompresji dużej liczby podobnych słówek w małym drzewie,
ale dostęp jest wolny.

Liczba danych - tekstów, opisów, jest dość duża, coś na poziomie do 10000 na plik, a plików może być dowolnie dużo, np. 500.
Wtedy jest problem z tymi tekstami, bo psują mi struktury danych - są zbyt wielkie, i zmiennej długości.

Zatem wymyśliłem sposób na pozbycie się tych tekstów z danych,
a zamiast nich pamiętać tylko numery - odsyłacze do zbioru samych tekstów.

Pytanie jak często będziesz aktualizować takie dane, jeśli rzadko, to może FSM będzie dobrym rozwiązaniem.

hauleth napisał(a):

Pytanie jak często będziesz aktualizować takie dane, jeśli rzadko, to może FSM będzie dobrym rozwiązaniem.

Na tym polega ten mój pomysł: wcale nie będę modyfikował danych w tej bazie!
Co znaczy że teksty w tej bazie nie będzą nigdy usuwane, ani zmieniane - raz wpisany pozostanie tam na wieki.

Będą tylko dodawane nowe teksty, i tylko takie których baza nie zawiera.

Jak dużo będzie tych tekstów i jak szybko będą wpisywane?
To nie ma znaczenia;
baza będzie rosnąć z czasem, np. milion pozycji na rok, czy na miesiąc, bez różnicy.