dcodeio / btree.js Goto Github PK

View Code? Open in Web Editor NEW

45.0 45.0 12.0 237 KB

A ridiculously lean B-tree of variable orders in plain JavaScript.

Home Page: http://dcode.io

License: Apache License 2.0

JavaScript 100.00%

btree.js's People

Contributors

Stargazers

Watchers

Forkers

tonistiigi sato-shi irrelon shangerbingenius charliexp slothy windcaller31 mmalmi manuelaguirre tyrell

btree.js's Issues

Wrong key deleted

Sometimes the wrong key is deleted. Example:

const Tree = btree.create(5, btree.numcmp);
const tree = new Tree();

for (const key of [7,6,1,5,4,8,2,3]) tree.put(key, key+"");
for (const key of [7,4,2,5]) tree.del(key);
console.log(tree.get(5)); // "5", but should be undefined
console.log(tree.get(3)); // undefined, but should be "3"

Any way to walkDesc with a limit on number of records?

This library is pretty awesome, thanks for spending the time to make it available to others.

I see tree.walk and tree.walkDesc take minKey and maxKey arguments. I was wondering if there was a valid case for them to also take a limit argument. During the walk, the search algorithm could keep track of the number of records returned and stop when limit is hit.

It looks like there's also an undocumented feature that if callback (passed to walkDesc) returns true, the loop is stopped. So I guess my calling function could keep track of the number of times callback is called, then return true when my limit is hit? Does that sound like a good way to use a limit?

Thanks again! This is rad.

put() should overwrite value if key exists

At the moment when you call put() with same key again it just returns false and doesn't update the value. To me it seems more logical to overwrite the old value.

btree.js/btree.js

Line 236 in 72edfb5

if (result.leaf) return false; // Key already exists

What makes it even harder is that because of the compilation phase I can't use treenode.search() to find the node and update the value manually. Compiler optimizes the leaf property away.

This would be a breaking change so I didn't make a PR yet but would like to get your thoughts.

Bug in tree.walkAsc()

I found a bug in tree.walkAsc(), demonstrated by the following script:

const Tree = btree.create(2, btree.numcmp)
var tree = new Tree()
var values = [1547020800,1547020860,1547020920,1547020980,1547021040,1547021100,1547021160,1547021220,1547021280,1547021340,1547021400,1547021460,1547021520,1547021580,1547021640,1547021700,1547021760,1547021820,1547021880,1547021940,1547022000,1547022060,1547022120,1547022180,1547022240,1547022300,1547022360,1547022420,1547022480,1547022540,1547022600,1547022660,1547022720,1547022780,1547022840,1547022900,1547022960,1547023020,1547023080,1547023140,1547023200,1547023260,1547023320,1547023380,1547023440,1547023500,1547023560,1547023620,1547023680,1547023740,1547023800,1547023860,1547023920,1547023980,1547024040,1547024100,1547024160,1547024220,1547024280,1547024340,1547024400,1547024460,1547024520,1547024580,1547024640,1547024700,1547024760,1547024820,1547024880,1547024940,1547025000,1547025060,1547025120,1547025180,1547025240,1547025300,1547025360,1547025420,1547025480,1547025540,1547025600,1547025660,1547025720,1547025780,1547025840,1547025900,1547025960,1547026020,1547026080,1547026140,1547026200,1547026260,1547026320,1547026380,1547026440,1547026500,1547026560,1547026620,1547026680,1547026740,1547026800,1547026860,1547026920,1547026980,1547027040,1547027100,1547027160,1547027220,1547027280,1547027340,1547027400,1547027460,1547027520,1547027580,1547027640,1547027700,1547027760,1547027820,1547027880,1547027940,1547028000,1547028060,1547028120,1547028180,1547028240,1547028300,1547028360,1547028420,1547028480,1547028540,1547028600,1547028660,1547028720,1547028780,1547028840,1547028900,1547028960,1547029020,1547029080,1547029140,1547029200,1547029260,1547029320,1547029380,1547029440,1547029500,1547029560,1547029620,1547029680,1547029740,1547029800,1547029860,1547029920,1547029980,1547030040,1547030100,1547030160,1547030220,1547030280,1547030340,1547030400,1547030460,1547030520,1547030580,1547030640,1547030700,1547030760,1547030820,1547030880,1547030940,1547031000,1547031060,1547031120,1547031180,1547031240,1547031300,1547031360,1547031420,1547031480,1547031540,1547031600,1547031660,1547031720,1547031780,1547031840,1547031900,1547031960,1547032020,1547032080,1547032140,1547032200,1547032260,1547032320,1547032380,1547032440,1547032500,1547032560,1547032620,1547032680,1547032740,1547032800,1547032860,1547032920,1547032980,1547033040,1547033100,1547033160,1547033220,1547033280,1547033340,1547033400,1547033460,1547033520,1547033580,1547033640,1547033700,1547033760,1547033820,1547033880,1547033940,1547034000,1547034060,1547034120,1547034180,1547034240,1547034300,1547034360,1547034420,1547034480,1547034540,1547034600,1547034660,1547034720,1547034780,1547034840,1547034900,1547034960,1547035020,1547035080,1547035140,1547035200,1547035260,1547035320,1547035380,1547035440,1547035500,1547035560,1547035620,1547035680,1547035740,1547035800,1547035860,1547035920,1547035980,1547036040,1547036100,1547036160,1547036220,1547036280,1547036340,1547036400,1547036460,1547036520,1547036580,1547036640,1547036700,1547036760,1547036820,1547036880,1547036940,1547037000,1547107200,1547107260,1547107320,1547107380,1547107440,1547107500,1547107560,1547107620,1547107680,1547107740,1547107800,1547107860,1547107920,1547107980,1547108040,1547108100,1547108160,1547108220,1547108280,1547108340,1547108400,1547108460,1547108520,1547108580,1547108640,1547108700,1547108760,1547108820,1547108880,1547108940,1547109000,1547109060,1547109120,1547109180,1547109240,1547109300,1547109360,1547109420,1547109480,1547109540,1547109600,1547109660,1547109720,1547109780,1547109840,1547109900,1547109960,1547110020,1547110080,1547110140,1547110200,1547110260,1547110320,1547110380,1547110440,1547110500,1547110560,1547110620,1547110680,1547110740,1547110800,1547110860,1547110920,1547110980,1547111040,1547111100,1547111160,1547111220,1547111280,1547111340,1547111400,1547111460,1547111520,1547111580,1547111640,1547111700,1547111760,1547111820,1547111880,1547111940,1547112000,1547112060,1547112120,1547112180,1547112240,1547112300,1547112360,1547112420,1547112480,1547112540,1547112600,1547112660,1547112720,1547112780,1547112840,1547112900,1547112960,1547113020,1547113080,1547113140,1547113200,1547113260,1547113320,1547113380,1547113440,1547113500,1547113560,1547113620,1547113680,1547113740,1547113800,1547113860,1547113920,1547113980,1547114040,1547114100,1547114160,1547114220,1547114280,1547114340,1547114400,1547114460,1547114520,1547114580,1547114640,1547114700,1547114760,1547114820,1547114880,1547114940,1547115000,1547115060,1547115120,1547115180,1547115240,1547115300,1547115360,1547115420,1547115480,1547115540,1547115600,1547115660,1547115720,1547115780,1547115840,1547115900,1547115960,1547116020,1547116080,1547116140,1547116200,1547116260,1547116320,1547116380,1547116440,1547116500,1547116560,1547116620,1547116680,1547116740,1547116800,1547116860,1547116920,1547116980,1547117040,1547117100,1547117160,1547117220,1547117280,1547117340,1547117400,1547117460,1547117520,1547117580,1547117640,1547117700,1547117760,1547117820,1547117880,1547117940,1547118000,1547118060,1547118120,1547118180,1547118240,1547118300,1547118360,1547118420,1547118480,1547118540,1547118600,1547118660,1547118720,1547118780,1547118840,1547118900,1547118960,1547119020,1547119080,1547119140,1547119200,1547119260,1547119320,1547119380,1547119440,1547119500,1547119560,1547119620,1547119680,1547119740,1547119800,1547119860,1547119920,1547119980,1547120040,1547120100,1547120160,1547120220,1547120280,1547120340,1547120400,1547120460,1547120520,1547120580,1547120640,1547120700,1547120760,1547120820,1547120880,1547120940,1547121000,1547121060,1547121120,1547121180,1547121240,1547121300,1547121360,1547121420,1547121480,1547121540,1547121600,1547121660,1547121720,1547121780,1547121840,1547121900,1547121960,1547122020,1547122080,1547122140,1547122200,1547122260,1547122320,1547122380,1547122440,1547122500,1547122560,1547122620,1547122680,1547122740,1547122800,1547122860,1547122920,1547122980,1547123040,1547123100,1547123160,1547123220,1547123280,1547123340,1547123400,1547193600,1547193660,1547193720,1547193780,1547193840,1547193900,1547193960,1547194020,1547194080,1547194140,1547194200,1547194260,1547194320,1547194380,1547194440,1547194500,1547194560,1547194620,1547194680,1547194740,1547194800,1547194860,1547194920,1547194980,1547195040,1547195100,1547195160,1547195220,1547195280,1547195340,1547195400,1547195460,1547195520,1547195580,1547195640,1547195700,1547195760,1547195820,1547195880,1547195940,1547196000,1547196060,1547196120,1547196180,1547196240,1547196300,1547196360,1547196420,1547196480,1547196540,1547196600,1547196660,1547196720,1547196780,1547196840,1547196900,1547196960,1547197020,1547197080,1547197140,1547197200,1547197260,1547197320,1547197380,1547197440,1547197500,1547197560,1547197620,1547197680,1547197740,1547197800,1547197860,1547197920,1547197980,1547198040,1547198100,1547198160,1547198220,1547198280,1547198340,1547198400,1547198460,1547198520,1547198580,1547198640,1547198700,1547198760,1547198820,1547198880,1547198940,1547199000,1547199060,1547199120,1547199180,1547199240,1547199300,1547199360,1547199420,1547199480,1547199540,1547199600,1547199660,1547199720,1547199780,1547199840,1547199900,1547199960,1547200020,1547200080,1547200140,1547200200,1547200260,1547200320,1547200380,1547200440,1547200500,1547200560,1547200620,1547200680,1547200740,1547200800,1547200860,1547200920,1547200980,1547201040,1547201100,1547201160,1547201220,1547201280,1547201340,1547201400,1547201460,1547201520,1547201580,1547201640,1547201700,1547201760,1547201820,1547201880,1547201940,1547202000,1547202060,1547202120,1547202180,1547202240,1547202300,1547202360,1547202420,1547202480,1547202540,1547202600,1547202660,1547202720,1547202780,1547202840,1547202900,1547202960,1547203020,1547203080,1547203140,1547203200,1547203260,1547203320,1547203380,1547203440,1547203500,1547203560,1547203620,1547203680,1547203740,1547203800,1547203860,1547203920,1547203980,1547204040,1547204100,1547204160,1547204220,1547204280,1547204340,1547204400,1547204460,1547204520,1547204580,1547204640,1547204700,1547204760,1547204820,1547204880,1547204940,1547205000,1547205060,1547205120,1547205180,1547205240,1547205300,1547205360,1547205420,1547205480,1547205540,1547205600,1547205660,1547205720,1547205780,1547205840,1547205900,1547205960,1547206020,1547206080,1547206140,1547206200,1547206260,1547206320,1547206380,1547206440,1547206500,1547206560,1547206620,1547206680,1547206740,1547206800,1547206860,1547206920,1547206980,1547207040,1547207100,1547207160,1547207220,1547207280,1547207340,1547207400,1547207460,1547207520,1547207580,1547207640,1547207700,1547207760,1547207820,1547207880,1547207940,1547208000,1547208060,1547208120,1547208180,1547208240,1547208300,1547208360,1547208420,1547208480,1547208540,1547208600,1547208660,1547208720,1547208780,1547208840,1547208900,1547208960,1547209020,1547209080,1547209140,1547209200,1547209260,1547209320,1547209380,1547209440,1547209500,1547209560,1547209620,1547209680,1547209740,1547209800,1547280000,1547280060,1547280120,1547280180,1547280240,1547280300,1547280360,1547280420,1547280480,1547280540,1547280600,1547280660,1547280720,1547280780,1547280840,1547280900,1547280960,1547281020,1547281080,1547281140,1547281200,1547281260,1547281320,1547281380,1547281440,1547281500,1547281560,1547281620,1547281680,1547281740,1547281800,1547281860,1547281920,1547281980,1547282040,1547282100,1547282160,1547282220,1547282280,1547282340,1547282400,1547282460,1547282520,1547282580,1547282640,1547282700,1547282760,1547282820,1547282880,1547282940,1547283000,1547283060,1547283120,1547283180,1547283240,1547283300,1547283360,1547283420,1547283480,1547283540,1547283600,1547283660,1547283720,1547283780,1547283840,1547283900,1547283960,1547284020,1547284080,1547284140,1547284200,1547284260,1547284320,1547284380,1547284440,1547284500,1547284560,1547284620,1547284680,1547284740,1547284800,1547284860,1547284920,1547284980,1547285040,1547285100,1547285160,1547285220,1547285280,1547285340,1547285400,1547285460,1547285520,1547285580,1547285640,1547285700,1547285760,1547285820,1547285880,1547285940,1547286000,1547286060,1547286120,1547286180,1547286240,1547286300,1547286360,1547286420,1547286480,1547286540,1547286600,1547286660,1547286720,1547286780,1547286840,1547286900,1547286960,1547287020,1547287080,1547287140,1547287200,1547287260,1547287320,1547287380,1547287440,1547287500,1547287560,1547287620,1547287680,1547287740,1547287800,1547287860,1547287920,1547287980,1547288040,1547288100,1547288160,1547288220,1547288280,1547288340,1547288400,1547288460,1547288520,1547288580,1547288640,1547288700,1547288760,1547288820,1547288880,1547288940,1547289000,1547289060,1547289120,1547289180,1547289240,1547289300,1547289360,1547289420,1547289480,1547289540,1547289600,1547289660,1547289720,1547289780,1547289840,1547289900,1547289960,1547290020,1547290080,1547290140,1547290200,1547290260,1547290320,1547290380,1547290440,1547290500,1547290560,1547290620,1547290680,1547290740,1547290800,1547290860,1547290920,1547290980,1547291040,1547291100,1547291160,1547291220,1547291280,1547291340,1547291400,1547291460,1547291520,1547291580,1547291640,1547291700,1547291760,1547291820,1547291880,1547291940,1547292000,1547292060,1547292120,1547292180,1547292240,1547292300,1547292360,1547292420,1547292480,1547292540,1547292600,1547292660,1547292720,1547292780,1547292840,1547292900,1547292960,1547293020,1547293080,1547293140,1547293200,1547293260,1547293320,1547293380,1547293440,1547293500,1547293560,1547293620,1547293680,1547293740,1547293800,1547293860,1547293920,1547293980,1547294040,1547294100,1547294160,1547294220,1547294280,1547294340,1547294400,1547294460,1547294520,1547294580,1547294640,1547294700,1547294760,1547294820,1547294880,1547294940,1547295000,1547295060,1547295120,1547295180,1547295240,1547295300,1547295360,1547295420,1547295480,1547295540,1547295600,1547295660,1547295720,1547295780,1547295840,1547295900,1547295960,1547296020,1547296080,1547296140,1547296200,1547366400,1547366460,1547366520,1547366580,1547366640,1547366700,1547366760,1547366820,1547366880,1547366940,1547367000,1547367060,1547367120,1547367180,1547367240,1547367300,1547367360,1547367420,1547367480,1547367540,1547367600,1547367660,1547367720,1547367780,1547367840,1547367900,1547367960,1547368020,1547368080,1547368140,1547368200,1547368260,1547368320,1547368380,1547368440,1547368500,1547368560,1547368620,1547368680,1547368740,1547368800,1547368860,1547368920,1547368980,1547369040,1547369100,1547369160,1547369220,1547369280,1547369340,1547369400,1547369460,1547369520,1547369580,1547369640,1547369700,1547369760,1547369820,1547369880,1547369940,1547370000,1547370060,1547370120,1547370180,1547370240,1547370300,1547370360,1547370420,1547370480,1547370540,1547370600,1547370660,1547370720,1547370780,1547370840,1547370900,1547370960,1547371020,1547371080,1547371140,1547371200,1547371260,1547371320,1547371380,1547371440,1547371500,1547371560,1547371620,1547371680,1547371740,1547371800,1547371860,1547371920,1547371980,1547372040,1547372100,1547372160,1547372220,1547372280,1547372340,1547372400,1547372460,1547372520,1547372580,1547372640,1547372700,1547372760,1547372820,1547372880,1547372940,1547373000,1547373060,1547373120,1547373180,1547373240,1547373300,1547373360,1547373420,1547373480,1547373540,1547373600,1547373660,1547373720,1547373780,1547373840,1547373900,1547373960,1547374020,1547374080,1547374140,1547374200,1547374260,1547374320,1547374380,1547374440,1547374500,1547374560,1547374620,1547374680,1547374740,1547374800,1547374860,1547374920,1547374980,1547375040,1547375100,1547375160,1547375220,1547375280,1547375340,1547375400,1547375460,1547375520,1547375580,1547375640,1547375700,1547375760,1547375820,1547375880,1547375940,1547376000,1547376060,1547376120,1547376180,1547376240,1547376300,1547376360,1547376420,1547376480,1547376540,1547376600,1547376660,1547376720,1547376780,1547376840,1547376900,1547376960,1547377020,1547377080,1547377140,1547377200,1547377260,1547377320,1547377380,1547377440,1547377500,1547377560,1547377620,1547377680,1547377740,1547377800,1547377860,1547377920,1547377980,1547378040,1547378100,1547378160,1547378220,1547378280,1547378340,1547378400,1547378460,1547378520,1547378580,1547378640,1547378700,1547378760,1547378820,1547378880,1547378940,1547379000,1547379060,1547379120,1547379180,1547379240,1547379300,1547379360,1547379420,1547379480,1547379540,1547379600,1547379660,1547379720,1547379780,1547379840,1547379900,1547379960,1547380020,1547380080,1547380140,1547380200,1547380260,1547380320,1547380380,1547380440,1547380500,1547380560,1547380620,1547380680,1547380740,1547380800,1547380860,1547380920,1547380980,1547381040,1547381100,1547381160,1547381220,1547381280,1547381340,1547381400,1547381460,1547381520,1547381580,1547381640,1547381700,1547381760,1547381820,1547381880,1547381940,1547382000,1547382060,1547382120,1547382180,1547382240,1547382300,1547382360,1547382420,1547382480,1547382540,1547382600,1547452800,1547452860,1547452920,1547452980,1547453040,1547453100,1547453160,1547453220,1547453280,1547453340,1547453400,1547453460,1547453520,1547453580,1547453640,1547453700,1547453760,1547453820,1547453880,1547453940,1547454000,1547454060,1547454120,1547454180,1547454240,1547454300,1547454360,1547454420,1547454480,1547454540,1547454600,1547454660,1547454720,1547454780,1547454840,1547454900,1547454960,1547455020,1547455080,1547455140,1547455200,1547455260,1547455320,1547455380,1547455440,1547455500,1547455560,1547455620,1547455680,1547455740,1547455800,1547455860,1547455920,1547455980,1547456040,1547456100,1547456160,1547456220,1547456280,1547456340,1547456400,1547456460,1547456520,1547456580,1547456640,1547456700,1547456760,1547456820,1547456880,1547456940,1547457000,1547457060,1547457120,1547457180,1547457240,1547457300,1547457360,1547457420,1547457480,1547457540,1547457600,1547457660,1547457720,1547457780,1547457840,1547457900,1547457960,1547458020,1547458080,1547458140,1547458200,1547458260,1547458320,1547458380,1547458440,1547458500,1547458560,1547458620,1547458680,1547458740,1547458800,1547458860,1547458920,1547458980,1547459040,1547459100,1547459160,1547459220,1547459280,1547459340,1547459400,1547459460,1547459520,1547459580,1547459640,1547459700,1547459760,1547459820,1547459880,1547459940,1547460000,1547460060,1547460120,1547460180,1547460240,1547460300,1547460360,1547460420,1547460480,1547460540,1547460600,1547460660,1547460720,1547460780,1547460840,1547460900,1547460960,1547461020,1547461080,1547461140,1547461200,1547461260,1547461320,1547461380,1547461440,1547461500,1547461560,1547461620,1547461680,1547461740,1547461800,1547461860,1547461920,1547461980,1547462040,1547462100,1547462160,1547462220,1547462280,1547462340,1547462400,1547462460,1547462520,1547462580,1547462640,1547462700,1547462760,1547462820,1547462880,1547462940,1547463000,1547463060,1547463120,1547463180,1547463240,1547463300,1547463360,1547463420,1547463480,1547463540,1547463600,1547463660,1547463720,1547463780,1547463840,1547463900,1547463960,1547464020,1547464080,1547464140,1547464200,1547464260,1547464320,1547464380,1547464440,1547464500,1547464560,1547464620,1547464680,1547464740,1547464800,1547464860,1547464920,1547464980,1547465040,1547465100,1547465160,1547465220,1547465280,1547465340,1547465400,1547465460,1547465520,1547465580,1547465640,1547465700,1547465760,1547465820,1547465880,1547465940,1547466000,1547466060,1547466120,1547466180,1547466240,1547466300,1547466360,1547466420,1547466480,1547466540,1547466600,1547466660,1547466720,1547466780,1547466840,1547466900,1547466960,1547467020,1547467080,1547467140,1547467200,1547467260,1547467320,1547467380,1547467440,1547467500,1547467560,1547467620,1547467680,1547467740,1547467800,1547467860,1547467920,1547467980,1547468040,1547468100,1547468160,1547468220,1547468280,1547468340,1547468400,1547468460,1547468520,1547468580,1547468640,1547468700,1547468760,1547468820,1547468880,1547468940,1547469000];

values.forEach(function(v) { tree.put(v, v+"") })

console.log('num values inserted = ' + values.length);

var firstKey = null, lastKey = null;
tree.walk(null, null, function(k, v) { firstKey = k; return true });
tree.walkDesc(null, null, function(k, v) { lastKey = k; return true });
console.log('firstKey = ' + firstKey)
console.log('lastKey = ' + lastKey)

var totalWalkCount = 0;
var totalWalkDescCount = 0;
tree.walk(1547100000, 1547443500, function(k, v) { totalWalkCount++ });
tree.walkDesc(1547100000, 1547443500, function(k, v) { totalWalkDescCount++ });

var totalInRangeActual = 0
values.forEach(function(v) { if (v >= 1547100000 && v <= 1547443500) { totalInRangeActual++ } })

console.log('tree.count(): ' + tree.count())
console.log('tree.count(1547100000, 1547443500): ' + tree.count(1547100000, 1547443500))
console.log('tree.walk(1547100000, 1547443500, ...) count: ' + totalWalkCount)
console.log('tree.walkDesc(1547100000, 1547443500, ...) count: ' + totalWalkDescCount)
console.log('totalInRangeActual: ' + totalInRangeActual)

output:

num values inserted = 1626
firstKey = 1547020800
lastKey = 1547469000
tree.count(): 1626
tree.count(1547100000, 1547443500): 0
tree.walk(1547100000, 1547443500, ...) count: 0
tree.walkDesc(1547100000, 1547443500, ...) count: 1084
totalInRangeActual: 1084

And so it appears a potential workaround is to use walkDesc.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.