スキップリスト
実装:
data-structures/skiplist// 実行:go test ./data-structures/skiplist/
二分探索木は入れる順で一本の鎖に崩れる。スキップリストは回転で直すのではなく、各ノードの高さをコイン投げで決めることで、入れる順を最初から見ないようにする。昇順に4000件入れても高さは13で、同じ入力で二分探索木の高さは3999になる。飛ばし読みの手数は件数の対数でしか伸びず、1万倍にしても3倍にしかならない。
この章で作るもの
二分探索木は挿入順によっては一本鎖に崩れた。 B-Treeはそれを「太らせて割る」で防いだ。スキップリストは第3の道をとる。 確率で平衡を保つ。ソート済み連結リストに、飛ばし読み用の疎な層を積むだけ。
順に見ていく。
- 上で飛ばし、下で詰める: 疎な段を積むだけで、たどる手数が件数の対数で止まる
- 入れる順を見ない: 高さをコイン投げで決めるので、昇順に入れても崩れない
- 回転がいらない: 直すのではなく、最初から偏らない形にしている
① 上で飛ばし、下で詰める
ソート済み連結リストは、検索が先頭から1つずつで O(n)。遅い。 そこで「1個おき」「4個おき」…と間引いた層を上に積むと、上の層で大きく飛ばして から下の層で詰められる。これは二分探索木の「半分ずつ捨てる」を リストで再現したようなもの。
L2: 1 ─────────────▶ 6 ─────────────▶ 17
L1: 1 ──────▶ 3 ───▶ 6 ─────▶ 9 ────▶ 17
L0: 1 ─▶ 3 ─▶ 6 ─▶ 7 ─▶ 9 ─▶ 12 ─▶ 17 ← 全要素(最下段)
↑7 はここ問題は「どのノードを上の層に含めるか」。きっちり1個おきに保つのは、挿入・削除のたびに 全体を組み直すことになって高くつく。スキップリストの発明は、それをコイン投げで 決めてしまうこと。
高さはコイン投げで決める
ノードを挿入するとき、コインを投げて表が出る限り高さを増やす。 高さ1になる確率が1/2、高さ2が1/4、高さ3が1/8…。平均すると、 ちょうど「半分が次の段に上がる」疎な階層が確率的にできあがる。
// node はキー・値と、各段での「次のノード」への参照 next を持つ。
// len(next) がこのノードの高さ。high なノードほど飛ばし読みに使われる。
type node struct {
key int
val int
next []*node // next[i] = 第 i 段での次のノード
}
// SkipList は先頭番兵 head を持つスキップリスト。
type SkipList struct {
head *node
level int // 現在使われている最大段数
count int
rng *rand.Rand
steps int // Search で進んだ手数の累計
}
// New は空のスキップリストを返す。
func New() *SkipList {
return &SkipList{
head: &node{next: make([]*node, maxLevel)},
level: 1,
rng: rand.New(rand.NewSource(1)),
}
}
// randomLevel はコイン投げで新ノードの高さを決める。
// 表が続く限り段を増やす: 高さ1が確率1/2、高さ2が1/4、高さ3が1/8…。
// この分布が「上の段ほど疎」を作り、対数性能を生む。
func (sl *SkipList) randomLevel() int {
lvl := 1
for lvl < maxLevel && sl.rng.Float64() < probability {
lvl++
}
return lvl
}きっちりした階層でなくても、期待値として対数の性能が出る。これが確率的平衡。 テストでは1万件入れて高さが対数オーダー(理想13、上限25)に収まることを確認している。
検索は上から降りていく
// Search は key の値を返す。上の段から降りていく。
// 各段で「次が key を超える手前」まで進み、超えたら1段下りる。
// 上の疎な段で大きく飛ばし、下の段で細かく詰める。これが飛ばし読みになる。
func (sl *SkipList) Search(key int) (int, bool) {
x := sl.head
for i := sl.level - 1; i >= 0; i-- {
for x.next[i] != nil && x.next[i].key < key {
sl.steps++
x = x.next[i]
}
sl.steps++ // 進めずに1段下りるのも1手として数える
}
x = x.next[0] // 最下段で1歩進むと候補
if x != nil && x.key == key {
return x.val, true
}
return 0, false
}上の段から始めて、「次のノードが key を超える手前」まで各段で進み、超えたら1段下りる。 上の疎な段で大きく飛ばし、下の段で細かく詰める。
試す: 7 や 17 を探すと、検索経路(緑)が上の段で大きく飛んで下の段で詰めるのが見える。 全ノードを1つずつ見ていないことに注目してほしい。
10ノードを挿入。高さはコイン投げで決まっている
挿入は各段の直前ノードを繋ぎ替える
// Insert は key=value を挿入(既存なら更新)する。
// まず各段で「key が入る位置の直前ノード」を update に記録し、
// 新ノードの高さを randomLevel で決めて、その高さぶんのポインタを繋ぎ替える。
func (sl *SkipList) Insert(key, value int) {
update := make([]*node, maxLevel)
x := sl.head
for i := sl.level - 1; i >= 0; i-- {
for x.next[i] != nil && x.next[i].key < key {
x = x.next[i]
}
update[i] = x // 第 i 段で key の手前に来るノード
}
if next := x.next[0]; next != nil && next.key == key {
next.val = value // 既存キーの更新
return
}
lvl := sl.randomLevel()
if lvl > sl.level {
// 新しい高さのぶん、head を直前ノードとして埋める。
for i := sl.level; i < lvl; i++ {
update[i] = sl.head
}
sl.level = lvl
}
n := &node{key: key, val: value, next: make([]*node, lvl)}
for i := 0; i < lvl; i++ {
n.next[i] = update[i].next[i]
update[i].next[i] = n
}
sl.count++
}検索と同じように降りながら、各段で「key が入る位置の直前ノード」を update に記録する。 新ノードの高さを決めたら、その高さぶんだけ update のポインタを繋ぎ替える。 木の回転は一切ない。ポインタの繋ぎ替えだけ。ここがスキップリストが 赤黒木より実装しやすいと言われる理由。
② 入れる順を見ない
二分探索木の弱点は、入れる順で形が決まってしまうことだった。昇順に入れれば、右へ右へ伸びる一本の鎖になる。
スキップリストは、この問題を直すのではなく持ち込まない。高さがコイン投げで決まるので、キーの並びも入れた順も形に影響しない。
同じ入力を両方に流して測るとこうなった(4000件を昇順に挿入):
| 高さ | |
|---|---|
| スキップリスト | 13 |
| 二分探索木 | 3999 |
木のほうは、高さが件数そのものになっている。1本の鎖になったということで、探すのに端から全部たどることになる。テストで、この差を固定した。
手数のほうも測れる。段を降りるのも1手として数え、件数を変えて全件を引いた平均がこうなる:
// Steps は Search で進んだ手数の累計を返す。
//
// 引いた回数で割れば、1回あたり何手たどったかになる。
// 上の段で飛ばせているなら、件数が増えても対数でしか伸びない。
func (sl *SkipList) Steps() int { return sl.steps }
// ResetStats は数え直す。
func (sl *SkipList) ResetStats() { sl.steps = 0 }
// Height は今使われている段数を返す。
func (sl *SkipList) Height() int { return sl.level }
// LevelCounts は各段に居るノードの数を返す。
//
// コイン投げで高さを決めているので、上へ行くほどおよそ半分ずつになる。
func (sl *SkipList) LevelCounts() []int {
out := make([]int, sl.level)
for i := 0; i < sl.level; i++ {
for x := sl.head.next[i]; x != nil; x = x.next[i] {
out[i]++
}
}
return out
}| 件数 | 1回引くのにたどる手数 | 高さ |
|---|---|---|
| 100 | 14.67 | 8 |
| 1,000 | 19.80 | 11 |
| 10,000 | 24.64 | 13 |
| 100,000 | 32.67 | 16 |
| 1,000,000 | 43.78 | 16 |
件数を1万倍にして、手数は3倍。件数に比例していたら100万手かかっていたところだ。テストで、100倍に増やしても手数が2倍を超えないことを固定した。
段ごとのノード数も、狙いどおりに減っている(10万件):
0段目 100000
1段目 50147 ← およそ半分
2段目 25137
3段目 12501
4段目 6310
...
15段目 4コイン投げが表を出し続ける確率が半分ずつ減るので、そのまま段の疎さになる。テストで、下から8段ぶんの比が 0.3〜0.7 に収まることを固定した。平均を狙って作っているのではなく、確率の形がそのまま構造になっている。
③ 回転がいらない
| 平衡の保ち方 | 実装の複雑さ | 特徴 | |
|---|---|---|---|
| 二分探索木 | 保たない | 最易 | 挿入順で崩れる |
| AVL / 赤黒木 | 回転 | 難(ケース分けが多い) | 決定的に O(log n) |
| B-Tree | 太らせて割る | 中 | ディスク向き |
| スキップリスト | 確率(コイン投げ) | 易 | 回転なし。並行化しやすい |
スキップリストの弱みは「確率的なので最悪ケースは保証されない」こと。ただ n が大きければ 最悪が起きる確率は無視できるほど小さく、実用上は問題にならない。
設計の観点
- 直すのではなく、持ち込まない: 偏りを検知して直す代わりに、偏りようのない決め方にする
- 確率でよい場面を見きわめる: 最悪は保証されないが、件数が大きければ起きない
- 手数を数えられるようにする: 「対数」は主張なので、件数を変えて測れる形にしておく
- 形が単純だと並行化しやすい: 回転が無いので、段やノード単位でロックを分けられる
- 順序を保つ代価を意識する: ハッシュマップより遅い代わりに、範囲で取り出せる
- 偏りの原因を消す: キーの並びを見ないと決めた時点で、入力を選ばれても崩せない
対照と実例
| 平衡の保ち方 | 最悪 | 実装 | 特徴 | |
|---|---|---|---|---|
| 二分探索木 | 保たない | 件数そのもの | 最も易しい | 入れる順で崩れる |
| AVL / 赤黒木 | 回転 | 対数 | ケース分けが多い | 決定的に対数 |
| B-Tree | 太らせて割る | 対数 | 中くらい | ディスク向き |
| スキップリスト | コイン投げ | 件数そのもの(実質起きない) | 易しい | 回転なし。並行化しやすい |
| ハッシュマップ | (順序を捨てる) | 件数そのもの | 易しい | 範囲では取り出せない |
裏どり:
- Pugh(1990): 原論文。「平衡木の確率的な代替」という題のとおり、回転を確率で置き換える提案になっている。論文自体が短い
- Redis の sorted set: スキップリストとハッシュを組み合わせて持つ。順位で取り出せるように、各段に「何個ぶん飛ぶか」(span)を持たせている
- LevelDB / RocksDB の MemTable: メモリ上の書き込みバッファがスキップリスト。書きながら読むので、並行化しやすさが効く
- Java の
ConcurrentSkipListMap: 標準ライブラリに並行版が入っている。回転が無いことが、ロックを細かく分けられる理由になる - 確率の扱い: 最悪は保証されないが、10万件で高さが 60 を超える確率は無視できるほど小さい。保証を諦める代わりに、実装の単純さを取っている
簡略化したこと
- 乱数シード固定: 再現性のため。実物はランダムシード
- 値は int・スコアなし: Redis の ZSET は「スコア順」に並べる。ここは単純なキー順
- span を持たない: 「上位 N 件」のような順位で取り出す用途には、各段の距離が要る
- 並行化なし: 段やノード単位のロックは入れていない。この構造の取り柄の1つを使っていない
- 範囲取り出しの API なし: 最下段をたどれば作れるが、用意していない
参考資料
- Skip Lists: A Probabilistic Alternative to Balanced Trees (Pugh, 1990) — 原論文。短くて読みやすい
- Redis: t_zset.c — 実物の ZSET 実装(span 付き)
- 実装: data-structures/skiplist