search

Level / memdown

In-memory abstract-leveldown store for Node.js and browsers.
MIT License
287 stars 37 forks source link

Sub-Module the functional-red-black-tree library #203

Closed MeirionHughes closed 4 years ago

MeirionHughes commented 4 years ago

I propose adding functional-red-black-tree either as a sub-module of memdown or simply duplicate the code into here. The library hasn't been meaningfully updated in 6 years.

Specifically it would open up the door to making changes to improve performance: specifically replacing the current find + update or insert with an upsert method; i.e. cut tree-traversal by half for new inserts.

I think there would also be an opportunity, in the future, to improve batch loading too.

alternatively, we could switch to functional-red-black-tree2 as @Kirill486 seems to have picked up the torch.

vweevers commented 4 years ago

The library hasn't been meaningfully updated in 6 years.

A testament to its quality 😉 I see no reason to believe that the project is dead (the open PRs are only related to TypeScript). If it is, I would prefer that someone takes over maintenance. In any case, I'm opposed to vendoring. Any improvements will also benefit the module by itself - which I've used in the past as a synchronous alternative to memdown.

Let's first just try PRs to functional-red-black-tree, for example for an upsert method.

MeirionHughes commented 4 years ago

okay fair enough. I spent some time trying to get into it last night; background reading on "purely functional" BST and trying to see how its done in the lib. need to do some more playing to fully understand the path-stacks though.

MeirionHughes commented 4 years ago

@vweevers yeah I see what you mean. its rock solid. Its performance is hard to beat - by a wide margin. thought I'd give a functional avl a go: I can't get close. even for basic find I'm 50% slower. :(