qwertie / btree-typescript Goto Github PK
View Code? Open in Web Editor NEWA reasonably fast in-memory B+ tree with a powerful API based on the standard Map. Small minified. Well documented.
License: MIT License
A reasonably fast in-memory B+ tree with a powerful API based on the standard Map. Small minified. Well documented.
License: MIT License
Is it possible that, when we loop and delete multiple entries from btree, some of the entries/keys in the tree becomes undefined?
Our config: we have entries around 1800, and the base was chosen as 10.
Is this to do with how the balancing logic works?
Is there a way we can do btree.indexOf(key)
in O(log(n)) instead of O(n) in the implementation? Currently I am just doing a forEach and counting.
Similarly, it would be awesome if the set and remove methods returned the position of the inserted or removed entries respectively instead of boolean. This would save a round trip to indexOf.
How could one approach a need to access values in the comparator?
We have a set of objects, where want to:
At first, I was manually maintaining Map<Foo['id'], Foo>
as the main collection of all objects plus Set<Foo['id']>
as a collection of IDs representing an order by some criteria (not relevant here, I believe) + another such set for sorting.
Now, I thought that re-implementing the main collection to BTree<Foo['id'], Foo>
with a custom comparator would serve me well…
…however, I need to have access to the Foo
objects (which are quite complex) to be able to provide the sorting behavior, but that gets me infinite recursion from calling get
in the comparator, since BTree
uses the comparator in the implementation of get
.
I must admit that I might be conceptually missing some bigger picture here since this data structure is entirely new to me (as I've started to play with this just a few hours ago)…
…however, it seems to me that my use-case could be achieved relatively easily if there was
Hello, thank you for providing high quality source code.
Q1. Is the reason why there is no 'find() method' only for 'Map Interface' compatibility?
Q2. Should I use 'values() iterable' instead?
Seems that Btree become corrupted (forgots some keys) after some operations.
Here is an example:
const BTree = require('sorted-btree').default;
const tree = new BTree();
const keys = new Set();
// tree and keys should always contain same keys
for (let i=0; ; i++) {
// add to both
tree.set(i, i);
keys.add(i);
if (tree.size > 25000 && i % 2 == 0) {
const key = Math.floor(i / 2);
// delete from both
tree.delete(key);
keys.delete(key);
for (let key of keys) {
if (!tree.has(key)) {
console.error('No key ' + key + ' found in tree at cycle', i);
process.exit(1);
}
}
}
}
Use version 1.2.1 of sorted-btree and Node 13.5.0.
Thank you, incredibly fast lib.
Without esm build i.e.
"build:esm": "tsc --module es2015 --target es5 --outDir dist/esm"
its impossible to use this library if "type": "module",
is set in package.json.
i.e having commonjs I need add .default
and this breaks typings
import BTree from 'sorted-btree';
var tree = new BTree.default<number, [number, number]>(undefined, (a, b) => a - b);
To have near zero setup of esm+commonjs support I can recoomend https://github.com/developit/microbundle
Tried to use your btree implementation today, but when importing as you stated, it returns an error that there is no exported member BTree. There is an EmptyBTree, but that isn't usable. The only things exported, according to intellisense, are the interfaces.
Since BTree
is optimized for implementing sets efficiently, I expected BTree<K, V>
to implement the ISortedSet<K>
interface as well.
If used as follows (which I expect to be the standard):
const myMap: IMap<K, V> = new BTree();
const mySortedMap: ISortedMap<K, V> = new BTree();
const mySet: ISet<K> = new BTree();
const mySortedSet: ISet<K> = new BTree();
the extra methods would not be exposed unless necessary.
I can work on it and open a PR to fix it, if there are no downsides.
Thanks for the nice project! ❤️
What would be the best method for serialization of a sorted btree (using interface ISortedMap
)?
Is it safe to use JSON.stringify, or would you recommend serializing the iterable and then reconstructing the tree from the resulting array?
const tree = new BTree()
get error
Uncaught TypeError: BTree is not a constructor
This seems to be an issue with 0 being falsy. I haven't tested on any of the other variants.
This package fails to webpack with our setup due to:
ERROR in ./node_modules/sorted-btree/b+tree.js 13:24-31
Critical dependency: require function is used in a way in which dependencies cannot be statically extracted
Looking at the javascript, the 'factory' function 'require' is being passed into never uses its first argument (the 'require'), so I replaced the call site's 'require' with undefined and it fixed the webpacking. This workaround is a kludge though: I believe this code is part of the generated module format related boilerplate, and should be fixed by changing the module type.
Looking at tutorials for making npm packages with typescript, module format commonjs seems to be preferred over umd (ex: https://itnext.io/step-by-step-building-and-publishing-an-npm-typescript-package-44fe7164964c ), and I suspect setting commonjs in tsconfig.json will fix this (all my team's internal packages use it, and it works fine with node and webpack).
Hi, this lib is awesome, thanks for your sharing.
but I had a little problem when I wanted to extend a .next() method to loop through the entire tree
this._cursor = undefined
...
BTree.prototype.nextCyclePair = function () {
var key = this._compare(this._cursor, this.maxKey()) >= 0 ? undefined : this._cursor
var it = this.entries(key, ReusedArray)
var r = it.next()
if (!r.done && key !== undefined && this._compare(r.value[0], key) <= 0) {
r = it.next()
}
this._cursor = r.value ? r.value[0] : r.value
return r.value
}
It works, but unfortunately, not threads safety,
if I call async functions in parallel ,
There is a probability that get the same result,
I think it's because .entries() returns a new iterator each time,
so it.next() could possible return a same pair
That's why this._cursor not work,
so, my question is
Is there a way to implement a thread-safe iterator?
Here's a quick & dirty implementation I wrote, base on Map
module.exports = class CycledMap extends Map {
constructor (...args) {
super(...args)
this._indexArr = this.setIndexArr()
this._index = 0
}
get index () {
return this._index >= this.size ? 0 : this._index
}
set index (index) {
this._index = index
}
getkey (index) {
return this._indexArr[index]
}
next () {
const key = this.getkey(this.index++)
return { [key]: this.get(key) }
}
setIndexArr () {
this._indexArr = [...this.keys()]
}
clear () {
super.clear()
this._index = []
}
delete (key) {
super.delete(key)
this.setIndexArr()
}
set (...args) {
super.set(...args)
this.setIndexArr()
}
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.