熊崎 宏樹:性能が安定して良いからです。インメモリ型だと計算やメモリのコストも問題になりますがディスク指向なRDBMSでは遅延の支配項はディスクアクセスです。ですのでクエリに対してディスクアクセスが何回実行される事になるかという期待値が性能に大きく響いてきます。それと逆順方向のイテレーションができないという問題もあります。 B+Treeはブランチノードがリンクのみしか持たないのでデータ総数に対して少ないブランチノード数でより多くのデータに対する参照を保持することができ、ディスク指向なRDBMSのバッファプールに対して少ない負荷で目的のデータに辿り着く事ができます。バッファプールのLRUがまともに機能している前提の上で「すべてのブランチノードがメモリに乗ってリーフノードは最近アクセスされたものだけが乗っている」が定常状態になることが期待されます。こうなればすべてのクエリに対してインデックス側のディスクアクセスは高々1回に絞れます。1ページあたり32KBでキーの長さが16バイト+ページIDが8バイトと仮定すると、ブランチノードあたり1333ノードへの参照ができるので2階建てのB+treeならブランチノード1ページがメモリに乗っていれば1,333リーフノードがアクセスできますし、3階建てのB+Treeなら1334ノードがメモリに乗っていれば1,776,889リーフノードがアクセスできます。階数ごとのページ数に対する効率が大変良いという利点があります。 Skip Listはそれと比べるとデータ総数に対してだいたい半分がレベル2、更にその半分がレベル3、更にその半分がレベル4…という感じの構造になっているのでディスクアクセスを高々1回に抑えたいと考えるとレベル2以上のノードをすべてメモリに乗せている必要があります。1,776,889リーフノードそれぞれにディスクアクセス高々1回でアクセスするためには888,444ページ程をメモリに乗せている必要があり、1344ノードで済むB+Treeより不利です。また確率的なデータ構造なので極端な場合すべてのノードが最高レベルになってしまう可能性もあり、そうなると探索がO(N)になってしまいます。ですのでSkip Listを好んで使っているRDBMSは多くないようです。 しかし実装が堅牢かつ明快になったり、並行処理の扱いがtreeより簡単である事も相まって、RedisとかSingleStore（旧称MemSQL）なんかはSkip Listを好んで使っているようです。