Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk...
by jstanley on Sunday March 10, 2024 @04:44AM
(#39657656)
I don't know anything about zip trees, but I'd think in a common scenario the memory addresses are reasonably consecutive. Would that be a problem? If not, why not just assign consecutive ranks in the first place?
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk...
by jpfr on Sunday March 10, 2024 @02:55PM
(#39661562)
The address is scrambled (similar to a random-number generator) to produce the rank. So consecutive locations do not hurt performance.
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk...
by hinkley on Sunday March 10, 2024 @06:41PM
(#39663113)
This link seems to be more approachable:
https://stackoverflow.com/questions/61944198/what-is-a-zip-t...
For a project I made a version that uses the memory location of the entries to construct the (random) rank on the fly.
So itβs a binary tree structure that requires the same memory as a linked list (two pointers) only!
https://github.com/open62541/open62541/blob/master/deps/zipt...