在大數據與鍵值存儲系統中，面對高度偏斜 (Skewed) 且缺乏事前分佈資訊的動態查詢負載，傳統跳躍列表 (Skip list) 往往因搜尋路徑長度未能適配資料熱度，導致存取效率受限。特別是在鍵值比較成本高昂 (如長字串) 的場景下，冗餘的搜尋步數將顯著放大系統延遲。針對此問題，本研究首先建構了一個理論上的理想跳躍列表模型，探討在已知存取分佈下最佳的層級配置，並於理論上證明，該結構期望搜尋步數將小於或等於該查詢機率分佈的 Shannon 資訊熵。
為使系統能在缺乏事前資訊的情況下達到此理論值，本研究進一步提出一種簡單的演算法——MiniGravity。該演算法透過「下沉驅動」機制與局部回饋計數器，在動態搜尋過程中自適應地調整層級，引導跳躍列表結構逼近上述理想模型。
實驗結果顯示，在 10^5、10^6 的資料量規模下，MiniGravity 成功展現其逼近理想模型的優勢，將平均搜尋步數從 37.89 步縮減至 19.80 步（減少近 48%），吞吐量較傳統Skip list 提升 35%，亦優於 Splay-list 的 19% 提升幅度。然而，本研究進一步的壓力測試界定了此機制的系統擴展邊界：當資料量跨越至 10^7 規模時，此規則會引發嚴重的結構退化。實驗數據顯示，單純的下沉機制在極端長尾分佈下會導致大量極罕見節點過度下沉且缺乏調整機會，一旦系統存取到這些節點，其龐大的單次搜尋成本便會導致整體平均步數暴增與效能崩潰。此發現為未來大規模自適應索引結構在設計回饋機制時，提供了實務參考。

In big data and key-value storage systems, traditional Skip lists suffer from limited access efficiency under highly skewed dynamic query workloads lacking prior distribution information. Redundant search steps significantly increase system latency, especially when key comparison costs are high. To address this, we first establish a theoretical ideal Skip list model to examine the optimal level configuration given a specific access distribution, and theoretically prove that its expected search steps are bounded by the Shannon entropy of the query probability distribution. We then introduce MiniGravity, a lightweight heuristic algorithm that uses a "demotion-driven" mechanism and local feedback counters to adaptively adjust levels during dynamic searches, guiding the structure toward the ideal model without prior knowledge. Experimental results at a 10^6 data scale under a Zipfian workload demonstrate that MiniGravity successfully approximates the ideal model, significantly reducing average search steps by nearly 48% (from 37.89 to 19.80) and improving throughput by 35% over the traditional Skip list, outperforming the Splay-list. However, stress testing at a 10^7 scale reveals the limits of this heuristic mechanism: extreme long-tail distributions cause rare nodes to be demoted excessively without chances for readjustment, leading to a massive spike in search steps and a performance collapse. This finding provides practical insights for designing feedback mechanisms in large-scale adaptive index structures.

[1] Apache HBase. https://hbase.apache.org/. Accessed: 2026-07-02.
[2] ConcurrentSkipListMap (java platform SE 6). https://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html. Accessed: 2026-07-02.
[3] Google/leveldb. https://github.com/google/leveldb. Accessed: 2026-07-02.
[4] PingCAP/Go-YCSB. https://github.com/pingcap/go-ycsb. Accessed: 2026-07-02.
[5] RocksDB | a persistent key-value store. http://rocksdb.org/. Accessed: 2026-07-02.
[6] Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing, 36(3):395–418, 2023.
[7] Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. Workload analysis of a large-scale key-value store. In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, pages 53–64, 2012.
[8] Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich. Biased skip lists. Algorithmica, 42(1):31–48, 2005.
[9] Rudolf Bayer and Edward McCreight. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, pages 107–141, 1970.
[10] Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan. Biased search trees. SIAM Journal on Computing, 14(3):545–568, 1985.
[11] Prosenjit Bose, Karim Douïeb, and Stefan Langerman. Dynamic optimality for skip lists and B-trees. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1106–1114, 2008.
[12] Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, and S. Muthukrishnan. A data structure for a sequence of string accesses in external memory. ACM Trans. Algorithms, 3(1):6:1–6:23, 2007.
[13] Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, and Shanmugavelayutham Muthukrishnan. Static optimality theorem for external memory string access. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 219–227. IEEE, 2002
[14] Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing, pages 143–154, 2010.
[15] Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 131–140, 2010.
[16] Mikhail Fomitchev and Eric Ruppert. Lock-free linked lists and skip lists. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, pages 50–59, 2004.
[17] Keir Fraser. Practical lock-freedom. Technical report, University of Cambridge, Computer Laboratory, 2004.
[18] Chunkai Fu, Brandon G. Nguyen, Jung Hoon Seo, Ryan Zesch, and Samson Zhou. Learning-augmented search data structures, 2025.
[19] Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. A provably correct scalable concurrent skip list. In Conference On Principles of Distributed Systems (OPODIS). Citeseer, volume 103, 2006.
[20] Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. A simple optimistic skiplist algorithm. In International Colloquium on Structural Information and Communication Complexity, pages 124–138. Springer, 2007.
[21] Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear. The Art of Multiprocessor Programming. Newnes, 2020.
[22] John Iacono. Alternatives to splay trees with o(log n) worst-case access times. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 516–522, 2001.
[23] Charles Martel. Self-adjusting multi-way search trees. Information Processing Letters, 38(3):135–141, 1991.
[24] Kurt Mehlhorn. Best possible bounds on the weighted path length of optimum binary search trees. In Automata Theory and Formal Languages: 2nd GI Conference Kaiserslautern, May 20–23, 1975, pages 31–41. Springer, 2005.
[25] Fei Mei, Qiang Cao, Fei Wu, and Hongyan Li. A concurrent skip list balanced on search. In International Workshop on Advanced Parallel Processing Technologies, pages 117–128. Springer, 2017.
[26] Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 73–82, 2002.
[27] J Ian Munro, Thomas Papadakis, and Robert Sedgewick. Deterministic skip lists. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 367–375, 1992.
[28] Yedam Na, Bonmoo Koo, Taeyoon Park, Jonghyeok Park, and Wook-Hee Kim. Esl: A high-performance skiplist with express lane. Applied Sciences, 13(17):9925, 2023.
[29] Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 317–328, 2014.
[30] William Pugh. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM, 33(6):668–676, 1990.
[31] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686, 1985.
[32] Zhongle Xie, Qingchao Cai, HV Jagadish, Beng Chin Ooi, and Weng-Fai Wong. Parallelizing skip lists for in-memory multi-core database systems. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 119–122. IEEE, 2017.
[33] Lu Xing, Venkata Sai Pavan Kumar Vadrevu, and Walid G. Aref. The ubiquitous skiplist: A survey of what cannot be skipped about the skiplist and its applications in big data systems. ACM Computing Surveys, 57(11):1–37, 2025.