Append-only B+ Tree on Node.js

github.com

37 points·indutny··6 comments

This is in-progress project too.

You may be interested in an append only B+Tree implementation in C: https://github.com/DanielWaterworth/AODBM

Since we're all sharing implementations, anyone interested in a similar data structure for C# can feel free to dig through (or use) my btree-based key value store:

https://github.com/kevingadd/DataMangler

Of interest might be the fact that it's based on memory-mapped files, and it supports multithreaded querying. Insertion is single-threaded, though.

Unfortunately, it uses a regular old B-Tree. I should probably change it to a B+ Tree for better range queries... didn't even know about that data structure until seeing this HN post. :)

Implement COLA and leap frog the competition: http://supertech.csail.mit.edu/papers/sbtree.pdf

You've probably seen it already, but cpervica also just open sourced his B+ tree component of Tarsnap.

http://www.tarsnap.com/kivaloo.html

It's a specialized key value store. I'm reading through the C code for it. It will be fun to read your code along with that - thanks for putting it out there.

Wow! It's amazing! Do you have any benchmark results of it? Don't you mind if I'll wrap it in a module for node.js?

The only benchmarking I've done is a simple single-threaded test from python. I got about 8000 inserts per second. If that sounds low, then you must take into account that each insert hits the disk, ie it's completely durable.

I don't mind you creating a wrapper by any means and you don't need my permission anyway; it's open-source.

NOTE: it doesn't do log-structuring or compaction atm so the file will just continue to grow.

Reply on news.ycombinator.com