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

61–70 of 72 posts

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

#62

Post by benibela »

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

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

#64

Post by thesz »

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.

You can split a collection of 2^(k-1)The merge operation is fast and cache oblivious. Thus, insertion into a set of these arrays is fast.

Query is not so fast - O(log^2N). But I can direct you to Cache-Oblivious Lookahead Arrays (COLA) paper where a technique to get back to O(logN) complexity for lookup is described.

Or you can simple merge these arrays into one at the bulk insertion end.

Source code (not mine): https://github.com/giannitedesco/cola

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

#65

Post by benibela »

winrid wrote: post #11

Very... Short article. Anyway my favorite kind of tree is the R tree if you want to go down the research rabbit hole.

That is like a German pun

tree is Baum

R tree could be called Raum.

Which means space, which fits, because the tree stores the keys spatially.

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

#66

Post by ryanmjacobs »

mden wrote: post #60
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

Oh shoot, I didn't even notice that. Looks like he's at a constant Happiness=100 though.

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

#67

Post by [deleted] »

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

[deleted]

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

#68

Post by winrid »

benibela wrote: post #65
winrid wrote: post #11

Very... Short article. Anyway my favorite kind of tree is the R tree if you want to go down the research rabbit hole.

That is like a German pun tree is Baum R tree could be called Raum. Which means space, which fits, because the tree stores the keys spatially.

I like it!

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

#69

Post by aboodman »

hyperpallium wrote: post #53
aboodman wrote: post #47

Earlier quoted context omitted.

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)

You're right!

But you can sort the second column of the index too. So in our case, the index would be sorted by dept id, then employee id.

  deptid  empid
  1       1
  1       3
  1       7
  1       10
  ...
  2       4
  2       5
  2       9
  ...
  3       2
  3       6
  3       8
Now if we just do the basic thing and run through the index in order, we'll end up doing m sorted scans of the employee table, where m is the number of unique department ids. Not ideal, but if departments are large, still far better than seeking each employee individually.

But we can do better: If there are relatively few departments, the database can put a cursor at the beginning of each run of them:

  deptid  empid
  1       1
Now the database can scan those cursors in parallel, merge sort them, and feed the result into scanning the employee id table. Now we again have a single sorted scan of the employee table, at the cost of m extra memory.

This isn't a general solution. If there are zillions of departments and each one has only a handful of employees, this doesn't work. And in modern databases low-cardinality indexes like our dept_emp_id index sometimes use more specialized data structures.

One of the beautiful/crazy things about working on databases is it's a product that promises an abstraction that can't actually be implemented perfectly in all cases. Databases uses all kinds of heuristics internally to decide different strategies to answer queries. And vendors are constantly refining, trying to get closer to an ideal they can never actually reach.

But this particular strategy is a common and important one and an example of why B-trees were so important to early relational systems.

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

#70

Post by sriram_malhar »

whitten wrote: post #54
sriram_malhar wrote: post #36

Earlier quoted context omitted.

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?

eh? I'm curious why you would ask that.
Post reply on HN