Redis のリーダーボード「ゲームのランキング上位 100」「フォロワー数順のユーザリスト」「最新ツイート 50 件」 ── これらすべて Sorted Set (ZSET) で実装され、その中身が Skip List。連結リストにショートカット層を確率的に追加するだけで O(log n) を実現する、エレガントなデータ構造。
1. これで何が動いているか
- Redis Sorted Set (ZSET): ランキング / 時系列
- LevelDB / RocksDB: MemTable の中核
- Apache Cassandra: SSTable インデックス
- Java ConcurrentSkipListMap: スレッドセーフな TreeMap
- etcd: メモリ内インデックス
2. 仕組みのざっくり
- 最下層 (level 0): ソート済みの連結リスト
- 上の層: 各要素を確率 p (典型 0.5) で持ち上げた要素のリスト
- 検索: 最上層から開始、「次が目的より小さければ進む、大きければ下の層へ」
- 挿入: 検索しながら経路を記録 → ランダムな高さで全層に挿入
- 期待計算量: 平均高さ 1/(1-p) = 2、検索 O(log n)
3. Python 実装 (動作確認済)
純粋 Python の Skip List
Python
import random
class SkipNode: def __init__(self, key, level): self.key = key self.forward = [None] * (level + 1)
class SkipList: def __init__(self, max_level=16, p=0.5): self.max_level = max_level self.p = p self.header = SkipNode(None, max_level) self.level = 0
def random_level(self): '''高さを確率的に決定 (期待値 1/(1-p))''' lvl = 0 while random.random() < self.p and lvl < self.max_level: lvl += 1 return lvl
def insert(self, key): update = [None] * (self.max_level + 1) cur = self.header # 検索しながら経路 (update) を記録 for i in range(self.level, -1, -1): while cur.forward[i] and cur.forward[i].key < key: cur = cur.forward[i] update[i] = cur
lvl = self.random_level() if lvl > self.level: for i in range(self.level + 1, lvl + 1): update[i] = self.header self.level = lvl
new = SkipNode(key, lvl) for i in range(lvl + 1): new.forward[i] = update[i].forward[i] update[i].forward[i] = new
def search(self, key): cur = self.header for i in range(self.level, -1, -1): while cur.forward[i] and cur.forward[i].key < key: cur = cur.forward[i] cur = cur.forward[0] return cur is not None and cur.key == key
def display(self): '''各層を可視化''' for i in range(self.level, -1, -1): keys = [] cur = self.header.forward[i] while cur: keys.append(cur.key) cur = cur.forward[i] print(f'Level {i}: {keys}')
# 動作確認random.seed(0)sl = SkipList()for x in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]: sl.insert(x)
sl.display()print(f'\n19 がある? {sl.search(19)}')print(f'100 がある? {sl.search(100)}')
# 実機実行例:# Level 0: [3, 6, 7, 9, 12, 17, 19, 21, 25, 26]# Level 1: [3, 6, 12, 19, 25]# ...# 19 がある? True, 100 がある? False4. Redis ZSET との関係
redis-py で Skip List ベースの Sorted Set
Python
# pip install redisimport redis
r = redis.Redis(host='localhost', port=6379, decode_responses=True)
# ZADD で score 付きでメンバー追加r.zadd('leaderboard', { 'alice': 95, 'bob': 80, 'carol': 100, 'dave': 75, 'eve': 88})
# 上位 3 件 (内部的には Skip List で O(log n))top3 = r.zrevrange('leaderboard', 0, 2, withscores=True)print(f'TOP 3: {top3}')
# alice の順位 (内部的には Skip List で O(log n))rank = r.zrevrank('leaderboard', 'alice')print(f'alice の順位: {rank + 1}')
# score 80-95 の範囲mid = r.zrangebyscore('leaderboard', 80, 95)print(f'80-95 の範囲: {mid}')5. 計算量比較
| 操作 | Skip List | Red-Black Tree | Hash Table |
|---|---|---|---|
| 検索 | O(log n) | O(log n) | O(1) |
| 挿入 | O(log n) | O(log n) | O(1) |
| 削除 | O(log n) | O(log n) | O(1) |
| 順位取得 | O(log n) | O(log n) | 不可 |
| 範囲取得 | O(log n + k) | O(log n + k) | O(n) |
| 実装難易度 | 易 | 難 (回転) | 中 |
6. メリットとデメリット
- メリット: 実装が圧倒的に簡単 (回転なし)
- メリット: Lock-Free / 並列化が容易 (各層を独立に操作可)
- メリット: 「順位」「範囲」操作が高速
- デメリット: ランダム性に依存 (最悪 O(n)、ただし確率的に稀)
- デメリット: メモリ局所性が悪い (B-Tree より遅い場合あり)
7. 次の話
EP.13 では LSM Tree (Log-Structured Merge Tree) を扱います。Cassandra / RocksDB / BigTable / DynamoDB が使う、書込み性能を最大化するストレージエンジンの仕組み。