FTA:

> Skiplists to the rescue! Or rather, a weird thing we invented called a “skiptree”…

I can't help but wonder. The article makes no mention of b-trees if any kind. To me, this sounded like the obvious first step.

If their main requirement was to do sequential access to load data, and their problem was how to speed up tree traversal on an ad-hoc tree data structure that was too deep, then I wonder if their problem was simply having tree nodes with too few children. A B+ tree specifically sounds to be right on the nose for the task.

▲

akoboldfrying 2 days ago | parent [-]

IIUC, 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.

▲

wwilson 2 days ago | parent | next [-]

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.

▲

torginus 2 days ago | parent | prev [-]

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.

	▲	akoboldfrying a day ago \| parent [-]
		You don't really have to pre-guess the number of rungs -- you can just have a linked list of them and add a new rung "on top" when necessary, because you always start at the top rung, and only ever move sequentially along a rung, or step down to the rung immediately below. The overhead of pointer chasing is pretty small because there will only be O(log n) rungs; you move between rungs roughly often as you move along them. Also you can freely choose the "compaction rate" (base of that logarithm) to be something other than 2 -- e.g., choosing 4 means half as many rungs (but ~twice as much wandering along each rung).