スキップリストは何に向いているか？

記事

• スキップリストの実用的な用途を探り、「skip trees」と呼ぶ拡張を提案しています。
• スキップリストは、平衡BST（二分探索木）より簡潔なコードで、順序付き反復とO(log n)操作を実現します。
• Skip treesは階層的な集約を加え、効率的なfold・範囲操作を可能にします。
• Antithesisがファジングで生成した構造化データを効率よくクエリする必要から着想を得ています。

ディスカッション

• antirezによる指摘：Redisのソート済みセットは、本番環境で最も広く使われているスキップリストの実装です。
• 懐疑派は、スキップリストはポインタが多く、キャッシュ局所性の面でB+ツリーに実際には劣ると指摘しています。
• ロックフリーなスキップリストは並行システムでの優位性として挙げられており、SingleStoreがその例です。
• LSMツリーのmemtable、鍵透明性ログ（key transparency logs）、台帳残高クエリへの活用も紹介されています。

HN（Hacker News）で議論を読む

原文（英語）: What are skiplists good for?