スキップリストは回転ではなくコイントスで平衡を保った

平衡木として構築された順序付き構造は、更新のたびに再平衡化が必要であり、それは回転、再彩色、慎重な不変条件を意味する。いずれも間違えやすく、並列化しにくい。

スキップリストはその仕組みを確率的な規則に置き換える。各ノードには急激に減少する分布から引いたレベルが与えられるため、大半は低く、少数が高くなり、探索は低いレベルの長い区間を飛び越えてから下へ降りることができる。

レベルはランダムであるため、各レベルあたりのノード数の期待値は幾何分布となり、探索、挿入、削除はいずれも期待値でO(log n)に収まる。コードは短く、事後の記帳作業も不要である。

平衡を保つのは回転ではなくコイントスである

ランダムなレベルにより、再平衡化のコードなしで高さの上限が得られる。

局所的でロックに適した操作により、並列化が容易になる。

単純さにより、維持すべき不変条件が少なくなり、間違える余地も減る。

決定的な再平衡化が高コストで誤りやすい部分である場合、それを正直なランダム性に置き換えよ。局所的で単純な操作により、手作業で維持する不変条件と同じ期待性能が得られる。

スキップリストはライブラリやデータベースにおいて木の標準的な代替手段となった。最も有名なのはRedisのソート済みセットであり、そこでは単純さが並行性と予測可能な性能を助けている。