Let’s Invent B(+)-Trees • Hacker News Board

Re: Let’s Invent B(+)-Trees

#21

Post by ar-nelson » Tue, Apr 28, 2020, 2:56 AM UTC

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

[2] https://github.com/ar-nelson/schemepunk/blob/master/btree.sl...

Re: Let’s Invent B(+)-Trees

#22

Post by aabbcc1241 » Tue, Apr 28, 2020, 2:59 AM UTC

I like this website, it's simple and up to the point. And it works without Javascript :)

Re: Let’s Invent B(+)-Trees

#23

Post by aabbcc1241 » Tue, Apr 28, 2020, 3:14 AM UTC

ar-nelson wrote: post #21

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 [2] https:…

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

Re: Let’s Invent B(+)-Trees

#24

Post by hyperpallium » Tue, Apr 28, 2020, 3:17 AM UTC

I understand that B+ trees made relational databases practical.

Is that true? How are they used (sorted, according to link)? How do B+ differ from B trees?

Re: Let’s Invent B(+)-Trees

#25

Post by auraham » Tue, Apr 28, 2020, 3:35 AM UTC

AlexeyMK wrote: post #10

That made sense. I was following along, and then all of a sudden, it just kind of ended. As a layman who doesn't clearly remember B Trees, it would be awesome to have even a sentence at the end, like ...and that's B Trees! Commonly used for storing fields in relational databases, filesystems, and more! For fellow laymen, https://en.wikipedia.org/wiki/B-tree isn't bad, but is there more?

Totally agree. The first example was clear and intuitive, but I was lost when the author outlined the idea of blocks indexing blocks indexing values. Maybe an additional example could clearify this subject, improving considerably the quality of the post.

Re: Let’s Invent B(+)-Trees

#26

Post by ar-nelson » Tue, Apr 28, 2020, 3:36 AM UTC

aabbcc1241 wrote: post #23

ar-nelson wrote: post #21

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 [2] https:…

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

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/

Re: Let’s Invent B(+)-Trees

#27

Post by shakna » Tue, Apr 28, 2020, 3:50 AM UTC

hyperpallium wrote: post #24

I understand that B+ trees made relational databases practical. Is that true? How are they used (sorted, according to link)? How do B+ differ from B trees?

They have some things that a relational database likes:

+ Fast search (log(N))

+ Insert/Delete are fast (O(N) ... Most of the time)

+ Iteration is fast (unlike a hash map or similar)

You could have a look at [0] for a deeper dive.

[0] https://cstack.github.io/db_tutorial/parts/part7.html

Re: Let’s Invent B(+)-Trees

#28

Post by why-el » Tue, Apr 28, 2020, 4:12 AM UTC

revertts wrote: post #15

why-el wrote: post #9

Earlier quoted context omitted.

> Nowadays even red-black trees aren't favored due to practical concerns like caches Not sure if that's true. In addition to the main linux trunk using them, Java 8 included them also as an improvement to their HashMap (I found this by googling), so I don't they are not favored anymore. Edit: language.

There are cases where you need them, but it's relatively rare, they definitely shouldn't be your first choice. I'm fuzzy on all the current Linux use cases, but do remember one of the main users of rb trees was CFS. It's a neat scheduling algorithm. Java 8 specifically: HashMap is implemented with linked list chaining. This is already not very performant, but you can only do so much with Java being a reference heavy…

I was not commenting on whether one should use it or not, just that it is still used and picked as recently as Java 8. We are in agreement for the rest of your post. :+1:

Re: Let’s Invent B(+)-Trees

#29

Post by aabbcc1241 » Tue, Apr 28, 2020, 4:16 AM UTC

ar-nelson wrote: post #26

aabbcc1241 wrote: post #23

Earlier quoted context omitted.

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

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 pers…

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

Re: Let’s Invent B(+)-Trees

#30

Post by kadoban » Tue, Apr 28, 2020, 4:17 AM UTC

ar-nelson wrote: post #26

aabbcc1241 wrote: post #23

Earlier quoted context omitted.

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

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 pers…

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