4 ms·
In theory, this could provide dramatic performance uplift if the splay is done along lines of an aggregate value function over the node contents, and the conten
by bob1029 5y ago
In theory, this could provide dramatic performance uplift if the splay is done along lines of an aggregate value function over the node contents, and the contents of the node are selected such that their aggregate value function is well-defined & ordered relative to other nodes. I've got an implementation I might try this with. There are a ton of directions you could take this in depending on specifically what you are trying to optimize for.
Looking at this from a mechanical sympathy perspective - If you are unable to batch tree operations for whatever reason, increasing fanout is a good intermediate answer since you can make your storage system do more effective work per I/O. You can't ever read or write in units smaller than 1 storage block, so maybe shoving more logical items into each block is where you need to look.
Practically, this is probably not feasible in a wide number of use cases. GUID/UUID keys (non-linear) would break this scheme in my mind.