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

41–50 of 72 posts

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

#41

Post by xxs »

why-el wrote: post #9
kccqzy wrote: post #8

Earlier quoted context omitted.

I don't know about you, but when I started learning data structures, my professor told me AVL trees lost the popularity battle with red-black trees, and people tended to use red-black trees more. He didn't mention AVL trees besides a footnote. Nowadays even red-black trees aren't favored due to practical concerns like caches, so I assume AVL trees are very niche.

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

The improvement of hashmap applies only to high collision nodes that also implement comparable. It's a very special case. java.util.TreeMap has always been a red/black one.

On a flip note: HashMap in Java is sort of jack of trades, it's node based which means it has poor memory/caching characteristics - around 36bytes per standard node (compared to ~10 for array backed one) - and Nodes+array tend to be top3 objects in heap dumps. The iteration is sort of 'random' (unlikely LinkedHashMap) which has been a source of lots of issues not manifesting during testing. However, it doesn't degrade in virtually any use case. Normally, I don't use it - either a custom one (CompactHashMap), LinkedHashMap (being the go to hashtable), or ConcurrentHahshMap.

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

#42

Post by xxs »

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…

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

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

#43

Post by hyperpallium »

shakna wrote: post #27
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

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

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

#46

Post by valera_rozuvan »

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?

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

#47

Post by aboodman »

hyperpallium wrote: post #43
shakna wrote: post #27

Earlier quoted context omitted.

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

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 doing one seek per join result doesn't work at all. You can add caching to disguise to some extent, but that costs memory.

Compare to B-Trees: You build an index on EMPLOYEE.DEPARTMENTID. That index is also a B-Tree. Because they are sorted, you can just walk both employee index and department table in parallel by id. You only need to do n/k seeks (where k is branching factor of the b-tree). You only need one record worth of caching per table (the one under the current cursor).

Bonus: because the indices are sorted, it's easy to pipeline each seek after the previous to further reduced the latency of the query.

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

#48

Post by thesz »

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 the logarithmic method - a way to create dynamic structures (fast to insert and query) from static ones (slow to insert, fast to query). Even sorted arrays can be made fast for insertion in this way.

Anyway, try to keep your insertion order as sorted as possible. Delay actual insertion into disk data if needed.

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

#49

Post by revertts »

xxs wrote: post #42
revertts wrote: post #15

Earlier quoted context omitted.

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…

>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 hash table off heap, or Project Valhalla bears fruit, it's hard to get the data layout you'd want for a really good implementation. So I agree it can be better, but it's going to be hard to get to best - hence my comment.

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

#50

Post by revertts »

why-el wrote: post #28
revertts wrote: post #15

Earlier quoted context omitted.

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:

Ah! I'm sorry, I had misinterpreted your original comment.
Post reply on HN