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.

ds.data-structures functional-programming db.databases

— 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

10

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

$O(\log_B n)$ $O(B)$ $O(1)$

$O(\lg w)$ $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