2 ms·
It's also that they are different data structures used historically for different things, no? It'd be interesting to see a high-fanout splay tree, not even 100
by crdrost 5y ago
It's also that they are different data structures used historically for different things, no?
It'd be interesting to see a high-fanout splay tree, not even 100% sure how it'd work. Do you splay just the one node up to the root and have to split/combine each splay? Or do you only splay the first node in a "chunk" up? Or the whole "chunk"? Is it better to do a B+ type of thing rather than a B-tree type of thing?
- bob1029 5y agoIn 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.