I had some time series data which was append only like this. I started looking into skip lists and realized I might as well make it deterministic where the height of a node is basically popcnt. It ended up looking and behaving a lot like this.
Cool! I thought about using skip lists a bunch before I settled on this, trying to think of various ways to reduce complexity and memory usage. My best skip lists designs still had some pointer overhead that the implicit approach avoids, but it was pretty small and they seemed reasonably simple. I briefly tried thinking of what an implicit skip list would be, but then just ended up thinking about implicit search trees.
Comments
I had some time series data which was append only like this. I started looking into skip lists and realized I might as well make it deterministic where the height of a node is basically popcnt. It ended up looking and behaving a lot like this.
Cool! I thought about using skip lists a bunch before I settled on this, trying to think of various ways to reduce complexity and memory usage. My best skip lists designs still had some pointer overhead that the implicit approach avoids, but it was pretty small and they seemed reasonably simple. I briefly tried thinking of what an implicit skip list would be, but then just ended up thinking about implicit search trees.