Czysto funkcjonalny odpowiednik B-Tree?

14

Badam pomysł napisania DBMS w czysto funkcjonalny sposób. Tradycyjna struktura danych używana do indeksowania to B-Tree. Chciałbym poznać jakiś czysto funkcjonalny odpowiednik B-Tree, który zostałby zoptymalizowany w celu zminimalizowania dostępu do dysku. Dzięki.

Tianyi Cui
źródło
Nie wiem zbyt wiele o tym, ale to wydaje się rozsądnym miejscem do rozpoczęcia.
Ritwik Bose
Mechko, myślę, że struktury danych nie pamiętające pamięci podręcznej zasadniczo nie podlegają czysto funkcjonalnym implementacjom.
jbapple 23.01.11

Odpowiedzi:

10

Wiem więcej o strukturach czysto funkcjonalnych niż strukturach pamięci zewnętrznej, ale spróbuję.

O(logbn)O(b)O(1)

O(lgw)w

Możesz obejrzeć tę prezentację o RethinkDB , która wykorzystuje czysto funkcjonalne struktury danych ze względu na koszt zapisu na dyskach SSD.

jbapple
źródło
4

Jeśli chcesz napisać czysto funkcjonalną bazę danych, prawdopodobnie powinieneś sprawdzić pracę doktorską Phila Trindera na ten temat. Ma rozdział o użyciu B-drzew.

Dominic Mulligan
źródło