4 ms·

This is weirdly relevant. I just finished implementing a persistent B-tree library in Scheme.[1][2] I don't know why B-trees aren't used more as a purely-funct

This is weirdly relevant. I just finished implementing a persistent B-tree library in Scheme.[1][2] I don't know why B-trees aren't used more as a purely-functional data structure. Once they get large enough, they don't move around much when changed; there is no rebalancing except on deletes, and even that only affects the direct path to the deleted node. [1] https://github.com/ar-nelson/schemepunk#b-trees https://github.com/ar-nelson/schemepunk#b-trees [2] https://github.com/ar-nelson/schemepunk/blob/master/btree.sld https://github.com/ar-nelson/schemepunk/blob/master/btree.sl...

aabbcc1241 6y ago
I like the concept of persistent B-tree, can you share about the storage mechanism?
- ar-nelson 6y ago
  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]
- aboodman 6y ago
  persistent (for both senses of the word) b-trees are used extensively in couchdb. You can read about their design here: https://guide.couchdb.org/draft/btree.html https://guide.couchdb.org/draft/btree.html
  - aabbcc1241 6y ago
    I know quite a number of 'production grade' databases are using B-Tree internally, even mysql. I'm more interested on tiny implementation that just map the tree into the harddisk, without other complex features.
sriram_malhar 6y ago
Log-structured-merge trees are that; they are not a functional data structure in memory, but on disk they are. For those who don't know about this, here's how it works: Construct a b-tree in memory ('level 0'). When it reaches a certain size, move it to disk (to L1, level 1) in a compact fashion (by building the tree from the leaf up. There is no need to keep spare space at any L1 node because it is a functional data structure, and won't be directly mutated. The L0-tree in RAM can now be scrapped, and built up from scratch with more insertions. Again, when it exceeds a threshold, the in-memory L0-tree and the on-disk L1 tree from earlier are merged to create a new L1 tree. This goes on until the L1 tree has grown beyond a level-1 threshold size (some k times the L0 size), at which point, the L1 tree is pushed into L2. And so on. L0 is in RAM, L1 and others are on disk. Lookups are more expensive because multiple trees may have to be consulted, but with a judicious use of multiple cores and bloom filters, that cost can be recouped. This avoidance of in-place mutations works esp. well with SSDs and other copy-on-write systems.
- whitten 6y ago
  What does the phrase "bloom filter" mean to you?
  - sriram_malhar 6y ago
    eh? I'm curious why you would ask that.
benibela 6y ago
I have implemented a HAMT (hash array mapped trie) in Pascal It has the same tree structure with a lot of children. But the hash is used as key, so they need no balancing. It is just assumed the hash is sufficiently well distributed.

aabbcc1241 6y ago

I like the concept of persistent B-tree, can you share about the storage mechanism?

ar-nelson 6y ago
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]
aboodman 6y ago
persistent (for both senses of the word) b-trees are used extensively in couchdb. You can read about their design here: https://guide.couchdb.org/draft/btree.html https://guide.couchdb.org/draft/btree.html
- aabbcc1241 6y ago
  I know quite a number of 'production grade' databases are using B-Tree internally, even mysql. I'm more interested on tiny implementation that just map the tree into the harddisk, without other complex features.

sriram_malhar 6y ago

Log-structured-merge trees are that; they are not a functional data structure in memory, but on disk they are. For those who don't know about this, here's how it works: Construct a b-tree in memory ('level 0'). When it reaches a certain size, move it to disk (to L1, level 1) in a compact fashion (by building the tree from the leaf up. There is no need to keep spare space at any L1 node because it is a functional data structure, and won't be directly mutated. The L0-tree in RAM can now be scrapped, and built up from scratch with more insertions. Again, when it exceeds a threshold, the in-memory L0-tree and the on-disk L1 tree from earlier are merged to create a new L1 tree. This goes on until the L1 tree has grown beyond a level-1 threshold size (some k times the L0 size), at which point, the L1 tree is pushed into L2. And so on. L0 is in RAM, L1 and others are on disk. Lookups are more expensive because multiple trees may have to be consulted, but with a judicious use of multiple cores and bloom filters, that cost can be recouped. This avoidance of in-place mutations works esp. well with SSDs and other copy-on-write systems.

whitten 6y ago
What does the phrase "bloom filter" mean to you?
- sriram_malhar 6y ago
  eh? I'm curious why you would ask that.

benibela 6y ago

I have implemented a HAMT (hash array mapped trie) in Pascal It has the same tree structure with a lot of children. But the hash is used as key, so they need no balancing. It is just assumed the hash is sufficiently well distributed.