Jednym z zastosowań trzymania struktury drzewiastej w pliku binarnym
może być katalog płyt CD/DVD.
Najprostszym sposobem byłoby trzymanie całego drzewka w pamięci i odczyt
oraz zapis w całości do pliku.
Gdy byłoby utworzone archiwum dysków DVD, wtedy przy otwieraniu
archiwum, całe byłoby wczytywane do drzewka. Jednak wczytywanie całości
zabierało by czas oraz program zabierał by jeszcze więcej pamięci.
Więc lepszą rzeczą byłoby otworzenie pliku i przeczytanie tylko katalogu
płytek, potem leniwie wypełniać drzewko - dla konkretnej płytki
przeczytać tylko jej katalog nadrzędny, itd.
To działa, gdy plik jest już utworzony, jednak gdy trzeba wykonać jakieś
operacje, zaczyna się trudność. Na przykład skanujemy jeszcze jedną
płytkę, usuwamy jakąś lub jeszcze raz przeskanowujemy istniejącą lub
podkatalog. Zanim nie zapiszemy, nowe dane będą w pamięci lub w pliku
tymczasowym ale większość danych będzie w niezmienionym pliku archiwum.
Jaki algorytm można do tego użyć? Przykładowo otworzyłem plik archiwum,
usunąłem z bazy informacje na temat jednej płytki DVD i teraz mam
przeszukać archiwum.

do góry

W dniu 2011-06-03 12:16, Borneq pisze:
> Jednym z zastosowań trzymania struktury drzewiastej w pliku binarnym
> może być katalog płyt CD/DVD.
> Najprostszym sposobem byłoby trzymanie całego drzewka w pamięci i odczyt
> oraz zapis w całości do pliku.
> Gdy byłoby utworzone archiwum dysków DVD, wtedy przy otwieraniu
> archiwum, całe byłoby wczytywane do drzewka. Jednak wczytywanie całości
> zabierało by czas oraz program zabierał by jeszcze więcej pamięci.
[...]

Podstawowe pytanie - czy to Cię boli faktycznie?
1. Czy masz taką bazę płyt, że nie mieści się w pamięci?
2. Czy wczytywanie trwa >0.2s?
Jeśli odpowiedzi są:
1. Mieści się, 2. Nie - zostaw w pamięci
1. Mieści się, 2. Tak - pomyśl o leniwym wczytywaniu liści.
1. Nie mieści się - B-drzewa będą pewnie odpowiedniejsze

--
Paweł Kierski
n...@p...net

do góry

W dniu 2011-06-03 12:27, Paweł Kierski pisze:
> Podstawowe pytanie - czy to Cię boli faktycznie?
> 1. Czy masz taką bazę płyt, że nie mieści się w pamięci?
> 2. Czy wczytywanie trwa >0.2s?
> Jeśli odpowiedzi są:
> 1. Mieści się, 2. Nie - zostaw w pamięci
> 1. Mieści się, 2. Tak - pomyśl o leniwym wczytywaniu liści.
> 1. Nie mieści się - B-drzewa będą pewnie odpowiedniejsze

Jeżeli chodzi o płytki to mam trzy bazy we WhereIsIt rozmiarów 50-70 MB,
razem 170 MB, przy dzisiejszych gigabajtowych pamięciach zmieści się w
pamięci, jednak wczytywanie trwało by trochę. Najchętniej zrobiłbym
leniwe wczytywanie liści wczytując do pamięci tylko katalogi
rozwiniętych węzłów, jednak jest problem z edycją - np. reskanuję któryś
dysk z innymi opcjami, np czytania archiwów przez co się powiększa ilość
danych.

do góry

W dniu 2011-06-03 13:17, Borneq pisze:
> Jeżeli chodzi o płytki to mam trzy bazy we WhereIsIt rozmiarów 50-70 MB,
> razem 170 MB, przy dzisiejszych gigabajtowych pamięciach zmieści się w
> pamięci, jednak wczytywanie trwało by trochę. Najchętniej zrobiłbym
> leniwe wczytywanie liści wczytując do pamięci tylko katalogi
> rozwiniętych węzłów, jednak jest problem z edycją - np. reskanuję któryś
> dysk z innymi opcjami, np czytania archiwów przez co się powiększa ilość
> danych.

Myślałem nad tym aby podgałąź oznaczać jako skasowaną i dodawać na końcu
dane i raz na jakiś czas kompaktować. Tak dzieje się z plikami grafiki
wektorowej i chyba też z bazami maili programów pocztowych. Jednak tu
mam wątpliwości:
- popsuje się kolejność rekordów do rekurencyjnego szukania
- to działa gdy cały czas mam otwarty plik i natychmiast modyfikuję;
jednak chciałbym aby modyfikacje były dopiero po zapisie, zapis może
długo trwać i po nim nie trzeba by kompaktować.

do góry

W dniu 2011-06-03 13:29, Borneq pisze:
> W dniu 2011-06-03 13:17, Borneq pisze:
>> Jeżeli chodzi o płytki to mam trzy bazy we WhereIsIt rozmiarów 50-70 MB,
>> razem 170 MB, przy dzisiejszych gigabajtowych pamięciach zmieści się w
>> pamięci, jednak wczytywanie trwało by trochę. Najchętniej zrobiłbym
>> leniwe wczytywanie liści wczytując do pamięci tylko katalogi
>> rozwiniętych węzłów, jednak jest problem z edycją - np. reskanuję któryś
>> dysk z innymi opcjami, np czytania archiwów przez co się powiększa ilość
>> danych.
>
> Myślałem nad tym aby podgałąź oznaczać jako skasowaną i dodawać na końcu
> dane i raz na jakiś czas kompaktować. Tak dzieje się z plikami grafiki
> wektorowej i chyba też z bazami maili programów pocztowych. Jednak tu
> mam wątpliwości:
> - popsuje się kolejność rekordów do rekurencyjnego szukania
> - to działa gdy cały czas mam otwarty plik i natychmiast modyfikuję;
> jednak chciałbym aby modyfikacje były dopiero po zapisie, zapis może
> długo trwać i po nim nie trzeba by kompaktować.

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-)

--
Paweł Kierski
n...@p...net

do góry

On 03/06/2011 11:16, Borneq wrote:
> Jednym z zastosowań trzymania struktury drzewiastej w pliku binarnym
> może być katalog płyt CD/DVD.
> Najprostszym sposobem byłoby trzymanie całego drzewka w pamięci i odczyt
> oraz zapis w całości do pliku.

Najprostszym sposobem byłoby skorzystanie z istniejącego rozwiązania.
SQLite czy coś w tym stylu nie daje rady?

do góry

On Fri, 03 Jun 2011 12:16:53 +0200, Borneq <b...@a...hidden.pl>
wrote:

>Jednym z zastosowań trzymania struktury drzewiastej w pliku binarnym
>może być katalog płyt CD/DVD.
>Najprostszym sposobem byłoby trzymanie całego drzewka w pamięci i odczyt
>oraz zapis w całości do pliku.
>Gdy byłoby utworzone archiwum dysków DVD, wtedy przy otwieraniu
>archiwum, całe byłoby wczytywane do drzewka. Jednak wczytywanie całości
>zabierało by czas oraz program zabierał by jeszcze więcej pamięci.
>Więc lepszą rzeczą byłoby otworzenie pliku i przeczytanie tylko katalogu
>płytek, potem leniwie wypełniać drzewko - dla konkretnej płytki
>przeczytać tylko jej katalog nadrzędny, itd.
>To działa, gdy plik jest już utworzony, jednak gdy trzeba wykonać jakieś
>operacje, zaczyna się trudność. Na przykład skanujemy jeszcze jedną
>płytkę, usuwamy jakąś lub jeszcze raz przeskanowujemy istniejącą lub
>podkatalog. Zanim nie zapiszemy, nowe dane będą w pamięci lub w pliku
>tymczasowym ale większość danych będzie w niezmienionym pliku archiwum.
>Jaki algorytm można do tego użyć? Przykładowo otworzyłem plik archiwum,
>usunąłem z bazy informacje na temat jednej płytki DVD i teraz mam
>przeszukać archiwum.

Slyszales o B-trees?

A.L.

do góry

Oczywiście B-Trees ale wykonanie tego czasowo to mision-imposible.
Dlatego dużo bardziej praktycznym rozwiązaniem jest sqlite.

do góry

On Fri, 03 Jun 2011 22:22:24 +0200, Szyk <s...@o...pl> wrote:

>Oczywiście B-Trees ale wykonanie tego czasowo to mision-imposible.

Dlaczego?...

A.L.

do góry

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.

do góry