3 ms·
Append-only B+ Tree on Node.js
This is in-progress project too.
- DanWaterworth 15y agoYou may be interested in an append only B+Tree implementation in C: https://github.com/DanielWaterworth/AODBM https://github.com/DanielWaterworth/AODBM
- indutny 15y agoWow! 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?
- DanWaterworth 15y agoThe 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.
- tom_b 15y agoYou've probably seen it already, but cpervica also just open sourced his B+ tree component of Tarsnap. http://www.tarsnap.com/kivaloo.html 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.
- kevingadd 15y agoSince 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 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. :)
- br1 15y agoImplement COLA and leap frog the competition: http://supertech.csail.mit.edu/papers/sbtree.pdf http://supertech.csail.mit.edu/papers/sbtree.pdf