Comparison by value about btree-typescript

[utdemir]

@kubijo I had similar challenges, so I implemented a small library on top of that (powered by another btree library). My intention was to allow different kinds of indexes/restrictions via combining different indexes: https://github.com/utdemir/composable-indexes

It's not used in production anywhere - but it might give you an idea.

(@qwertie - this is a bit off-topic so feel free to delete it if you don't want it here)

[qwertie]

Sorry, I don't understand what you mean. Could you give an example of data you want to store, and how you want lookups to work?

[kubijo]

Let's try again then :-)

It's a monitoring app where there can be thousands of devices, each represented by an object with an ID, static data and live data. The static data will hopefully only get populated once, the live ones will stream in quite ferociously (like tens of milliseconds - albeit we'll limit this to a set visible on a table page).

---

Now, I need to have:

• a very performant lookup by the device ID (hence the Map<id, obj>)
• sorting of the whole dataset by one of the attributes (it seems like only the static ones, as it stands now)
• filtering of the whole dataset by potentially many of the attributes (again, hopefully now and ever only by the static ones)

---

Our idea then was to have a central collection be some kind of sorted map, where:

• sorting is taken care of upon insertion, and we'll only trigger full re-sort when criteria change based on the user's input
• retrieval is fast
• update that doesn't change order is fast (see the live data)
• filtering can be done on the fly while rendering
• …and then there is hopefully only slicing for a pager and a render

---

As we're speaking, I have tried several implementations of btree collections and starting to lose my grip on reality because every time there is some fundamental flaw and/or limitation like:

• duplicate keys are being stored in all of them (I am possibly doing something dumb here, but I'd hope that any kind of set collection will not let me store duplicate keys into it, no matter what I do… and my keys are just bigint)
• keys are limited to number

My solution to sorting only by keys was to have an extra class where I have a Map<id, obj> plus a sorted collection that only stores the IDs.
This allowed me to access values in the sorter, but as already mentioned, every time I got duplicate keys after few updates.

[qwertie]

I'm not sure if the word "key" means something different than "id" here. But no, BTree does not allow duplicate keys.

If you want to sort by a static attribute, that seems like a simple and straightforward use of BTree (although (1) you may not need BTree at all in this case: you could just use Array.sort() unless the list is very long and you need good insertion performance, (2) BTree does not allow duplicate keys so if multiple objects can have the same static attribute, you need to compute a unique key derived from the static attribute plus something else such as the object's unique ID.)

If you want to sort by a dynamic attribute, you might do this by having a fancier object-modification procedure: (1) remove the object from the BTree before changing the attribute, (2) change the attribute, (3) re-insert the object in the BTree.

[kubijo]

@utdemir I have resorted to dropping the whole Btree side of things in the end and built the thing on a backing of Map<K, V> + Set<K> (filtered) + Set<K> (sorted), using new Set(Array.from(all.keys()).sort(fn))…

…we'll see about performance, I guess. Thanks for the tip though, it might yet become relevant if the mentioned solution proves insufficient

[qwertie]

Understood.