Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Let’s Invent B(+)-Trees

shachaf.net

Post reply on HN
Print view View original

51–60 of 72 posts

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

#51

Post by ar-nelson »

kadoban wrote: post #30
ar-nelson wrote: post #26

Earlier quoted context omitted.

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

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

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

#52

Post by xxs »

revertts wrote: post #49
xxs wrote: post #42

Earlier quoted context omitted.

>you can only do so much with Java being a reference heavy language. This is definitely not true, implementing array based hashtable is trivial and outperforms in most cases java.utl.HashMap. It's just the decision to have LinkedHashMap (in java 1.2) extending HashMap crippled the latter. The issue has been discussed quite a few times in java core mailing list.

I agree, HashMap is unnecessarily hamstrung because the API requirements push it into a bucket chained implementation (C++ also made this mistake and is one of the downsides of std::unordered_map). And you can definitely write a faster implementation with an array based hashtable. But I still stand by "you can only do so much being a reference heavy language." Unless you stick to purely primitive types, implement the…

I do agree data layout is hard - pretty much direct byte buffers (off heap) and some poor man's memory manager (plus serialization/desirilization code).

Project Valhalla and structs is something people have been asking for since Java 1.4 or so. Still nowhere near. And indeed, "best" would take a custom implementation, case by case. It's doable, but usually very far from pretty.

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

#53

Post by hyperpallium »

aboodman wrote: post #47
hyperpallium wrote: post #43

Earlier quoted context omitted.

Thanks, sounds like sorting is an implementation detail, and not the main benefit in itself.

Imagine you're doing: SELECT * FROM EMPLOYEE, DEPARTMENT WHERE EMPLOYEE.DEPARTMENTID = DEPARTMENT.ID The naive thing would be to iterate employees and for each one read the corresponding department. However that would mean one disk seek per employee. Disk seeks on the rotational disks relational dbs were developed for took hundreds of ms to complete. Even today's rotational disks have seeks that take dozens of ms. So…

Thanks, makes sense! I've once before seen comparing sorted values is faster, even when not all match.

If "building an index" means it's just the indices (not all rows of the table), doesn't that indirection mean an extra seek to get the full row? (I probably have a fundamental misunderstanding here)

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

#54

Post by whitten »

sriram_malhar wrote: post #36
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:…

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…

What does the phrase "bloom filter" mean to you?

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

#55

Post by derefr »

Does anyone here know if there’s a data structure more ideal (i.e. lower-overhead) than a B+-tree for holding onto large amounts of on-disk data, if you can constrain the operations you’re going to do? Personally, in my workload, I know I’m never going to delete from the tree, only insert and query. Does this “get me” anything?

For another consideration: B+-trees (or trees generally) aren’t necessarily the best when the workload is mostly appends to the end of the keyspace. Is there an on-disk data structure that is tuned for mostly-append, rarely-insert workloads? Or how about for insert workloads, where each insert is actually a batch of inserts of a large contiguous range of sorted keys? (I’ve observed that this workload makes LevelDB fall over, so LSM trees aren’t it.)

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

#56

Post by senderista »

thesz wrote: post #48
valera_rozuvan wrote: post #46

While implementing, I found that there is a large number of disk hops (and hence greater time required to read), and accessing data is slow. Only a chunk of data fits in a disk block (remember, there is a predefined size limit for blocks). How to get around this?

B+-trees degrade quite fast with the slightest hint of randomness in the inserted data. To get around this unfortunate property people invented Log-structured Merge Trees - you keep new part of your data which is easy to insert randomly to and once in a while merge it (as sorted data!) with main data. This way degradation is greatly reduced at the expense of reading speed in case of merge. BTW, LTMs are a variant of…

Could you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.

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

#57

Post by kyralis »

derefr wrote: post #55

Does anyone here know if there’s a data structure more ideal (i.e. lower-overhead) than a B+-tree for holding onto large amounts of on-disk data, if you can constrain the operations you’re going to do? Personally, in my workload, I know I’m never going to delete from the tree, only insert and query. Does this “get me” anything? For another consideration: B+-trees (or trees generally) aren’t necessarily the best when…

I've personally used a B+Tree variant in this case with special-cased insert rules. Rather than splitting nodes when they're full, if they're filled due to appending at the right-hand-side we simply start the next leaf (or next interior + leaf pair) during insert. So, for pure in-order insertions, we end up with a maximally efficient tree with no splits needed; the rest of the logic still works if you then go back and need to update or insert into the middle of the tree at a later date.

I'm sure I'm not the only one with that particular implementation, but I'm not aware of any named algorithm/variant for it.

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

#58

Post by JoeAltmaier »

senderista wrote: post #56
thesz wrote: post #48

Earlier quoted context omitted.

B+-trees degrade quite fast with the slightest hint of randomness in the inserted data. To get around this unfortunate property people invented Log-structured Merge Trees - you keep new part of your data which is easy to insert randomly to and once in a while merge it (as sorted data!) with main data. This way degradation is greatly reduced at the expense of reading speed in case of merge. BTW, LTMs are a variant of…

Could you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.

Interval-halving? Is that a thing with trees?

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

#59

Post by ratmice »

aabbcc1241 wrote: post #29
ar-nelson wrote: post #26

Earlier quoted context omitted.

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

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

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

#60

Post by mden »

ryanmjacobs wrote: post #34

Haha, his web directory layout cracked me up. After reading, I thought to myself, "Hmm... I wonder what else he has written. I'll navigate upwards a level to https://shachaf.net/w "... It returns a blank page with the letter "w". That actually made me laugh out loud. "Ah, shucks. Let's go up again." Returns a non-styled page that reads "Success!".

And then when you click on Success you get this graph (which is a bit sad) - https://shachaf.net/pet.txt
Post reply on HN