alt Hacker NewsIIUC, the tree structure is the very thing they're trying to store and query -- it's not merely an artefact of a data structure that they're using to store something else (the way a B+ tree or binary tree used to store, say, a set of product names would be). If their tree has long paths, it has long paths.
Replies
torginus • yesterday at 2:16 PM
The nice thing with skip lists, is all 'rungs' of the list are stored in an array for a given node, so there's a lot less pointer chasing.
The not so nice thing about it is that you have to pre-guess how deep your tree will be and allocate as many slots, or otherwise itll degrade into a linked list when you run out of rungs, or you end up wasting space.
➕ show 1 reply
Author here. That’s right — the challenge was representing a tree in an existing SQL database that we’d chosen for its pricing model. I think encoding a B-tree in SQL would be a lot less fun even than what we did.