4 ms·

I guess I should have disambiguated my usage of "persistent". In this case it refers to a purely-functional data structure[1], not a data structure that is pers

I guess I should have disambiguated my usage of "persistent". In this case it refers to a purely-functional data structure[1], not a data structure that is persisted to disk. Inserting an item into a persistent B-tree produces a new tree, while leaving the old one intact. Ideally, this is done with minimal copying; unchanged subtrees are just pointers to the same subtrees in the old tree. This is very similar to persistent hash tries, which are used by purely-functional languages like Haskell. But I designed this B-tree library as an implementation of SRFI 146, which uses a comparison function, not a hash function, to create a key-value mapping. If you're interested in B-trees being persisted to disk, that's how most databases and most filesystems already work. [1] https://www.geeksforgeeks.org/persistent-data-structures/ https://www.geeksforgeeks.org/persistent-data-structures/

aabbcc1241 6y ago
I see, the javascript world usually it call the "persistent" data structure as "immutable" data structure
- kadoban 6y ago
  Yeah that's the usual terminology in JS world. Persistence (the naming) comes out of algorithm theory, which IMO has pretty poor naming in general (dynamic programming and cache-oblivious also come to mind as unfortunate names). Not entirely sure why that is. There's a few "levels" of persistence available, just as an aside. Immutability I think corresponds to the ~strongest level, but also means it can be hardest to achieve. One easier version allow only _querying_ old versions of the data structure for instance, no modifications except at the tip. Sometimes that's enough.
- ratmice 6y ago
  There is also a bit of weirdness here in that they aren't really the same thing, For example see this persistent union-find which is not immutable, but ensures its side-effects are safely hidden. https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf
kadoban 6y ago
Persistent B-trees do seem like they'd work fine. You will have to copy whole blocks that get modified, but I don't think that should hurt much. I'm fairly curious how benchmarks will look compared to the usual choices (Haskell has what, finger trees and radix trees or something? And red-black or AVL have persistent implementations all over of course.)
- ar-nelson 6y ago
  The reference implementation of SRFI 146 (persistent mappings) is a red-black tree[1]. I benchmarked my B-tree implementation against it and found that, in almost every R7RS Scheme, constructing small trees (~100 elements) and querying and deletion on large trees (~10,000 elements) was 2-3 times faster than red-black trees. The major difference was constructing large trees, which could be easily 10 times faster. [1] https://srfi.schemers.org/srfi-146/srfi-146.html https://srfi.schemers.org/srfi-146/srfi-146.html
- deleted 6y ago
  [deleted]

aabbcc1241 6y ago

I see, the javascript world usually it call the "persistent" data structure as "immutable" data structure

kadoban 6y ago
Yeah that's the usual terminology in JS world. Persistence (the naming) comes out of algorithm theory, which IMO has pretty poor naming in general (dynamic programming and cache-oblivious also come to mind as unfortunate names). Not entirely sure why that is. There's a few "levels" of persistence available, just as an aside. Immutability I think corresponds to the ~strongest level, but also means it can be hardest to achieve. One easier version allow only _querying_ old versions of the data structure for instance, no modifications except at the tip. Sometimes that's enough.
ratmice 6y ago
There is also a bit of weirdness here in that they aren't really the same thing, For example see this persistent union-find which is not immutable, but ensures its side-effects are safely hidden. https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf

kadoban 6y ago

Persistent B-trees do seem like they'd work fine. You will have to copy whole blocks that get modified, but I don't think that should hurt much. I'm fairly curious how benchmarks will look compared to the usual choices (Haskell has what, finger trees and radix trees or something? And red-black or AVL have persistent implementations all over of course.)

ar-nelson 6y ago
The reference implementation of SRFI 146 (persistent mappings) is a red-black tree[1]. I benchmarked my B-tree implementation against it and found that, in almost every R7RS Scheme, constructing small trees (~100 elements) and querying and deletion on large trees (~10,000 elements) was 2-3 times faster than red-black trees. The major difference was constructing large trees, which could be easily 10 times faster. [1] https://srfi.schemers.org/srfi-146/srfi-146.html https://srfi.schemers.org/srfi-146/srfi-146.html
deleted 6y ago
[deleted]