W dniu 2011-06-03 13:38, Paweł Kierski pisze:
> Coraz bardziej widzę B-drzewa: kolejność jest zachowana, na raz przy
> zapisie modyfikujesz co najwyżej kilka węzłów - najczęściej jeden.
> Fakt, że węzeł będzie miał kilka(naście)KB raczej nie powinien
> przeszkadzać 8-)

B-drzewa świetnie mogą nadać się przy tworzeniu bazy danych, zdaje się
że SQLite je używa. Jednak mam trochę inną sytuację. To że B-drzewa
wypełniane są od 50 do 100% to jeszcze mały problem - co najwyżej
średnio będą wypełnione w 75 procentach.
Nie widzę natomiast w jaki sposób zastosować je do problemu. W B-tree
mamy wypełnienie węzła od n/2 do n, podczas gdy ja mam dowolną ilość
podgałęzi w węźle od zera do tysięcy. Ponadto w B-drzewach raczej każda
zmiana typu dodanie węzła powoduje zapis na dysku. U mnie zmiany będą w
pamięci a zapis na dysk może trochę trwać.
Myślę nad rozwiązaniem gdzie węzły będą reprezentowane przez klasy w
pamięci, tak jak węzeł root. W węźle powinna być lista wskaźników do
innych węzłów albo indeks pozycji w pliku wraz z numerem pliku. Root
wskazywał by zarówno na węzły w pamięci jak i na plik, z kolei pozostałe
węzły tak samo, aż na samym końcu liśćmi byłyby rekordy w plikach.