DBMS Indexology

This repository contains a list of papers that focus on the design and implementation of index structures in modern database management systems (DBMSs). To better exhibit the design trend in this research area, this reading list is intended to only contain high-quality papers published in top-tier conferences/journals. If you have any paper in mind that you think awesome and would fit in this list, please feel free to send a pull request.

---

Contents

• Surveys
• SSD-Based Tree Indexing
• NVM-Based Tree Indexing
• In-Memory Tree Indexing
• Bitmap Indexing
• Hash Indexing
• Approximate Indexing

---

Surveys

• D. Lomet, The Evolution of Effective B-tree: Page Organization and Techniques: A Personal Account, in ACM SIGMOD Record, 2001.
• G. Graefe, A Survey of B-Tree Locking Techniques, in TODS, 2010.
• G. Graefe, Modern B-tree techniques, in Foundations and Trends in Databases, 2011.

HDD-Based Tree Indexing

• R. Bayer, et al., Organization and Maintenance of Large Ordered Indices, in SIGFIDET, 1970. (original B-Tree paper)
• R. Bayer, et al., Prefix B-Trees, in TODS, 1977.

SSD-Based Tree Indexing

• Y. Li, et al., Tree Indexing on Solid State Drives, in VLDB, 2010.

NVM-Based Tree Indexing

• S. Chen, et al., Persistent B+-Trees in Non-Volatile Main Memory, in VLDB, 2015.
• I. Oukid, et al., FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory, in SIGMOD, 2016.
• S. Lee, et al., WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems, in FAST, 2017.

In-Memory Tree Indexing

• T. Lehman, et al., A Study of Index Structures for Main Memory Database Management Systems, in VLDB, 1986.
• J. Rao, et al., Cache Conscious Indexing for Decision-Support in Main Memory, in VLDB, 1999.
• J. Rao, et al., CSB+Tree Making B+-Trees Cache Conscious in Main Memory, in SIGMOD, 2000.
• M. Bender, et al., Cache-Oblivious Streaming B-Trees, in SPAA, 2007.
• C. Kim, et al., FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs, in SIGMOD, 2010.
• Y. Mao, et al., Cache Craftiness for Fast Multicore Key-Value Storage, in EuroSys, 2012.
• J. Levandoski, et al., The Bw-Tree: A B-tree for New Hardware Platforms, ICDE, 2013.
• V. Leis, et al., The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases, in ICDE, 2013.
• V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016.
• H. Zhang, et al., Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes, in SIGMOD, 2016.
• R. Binna, et al., HOT: A Height Optimized Trie Index for Main-Memory Database Systems, in SIGMOD, 2018.

Bitmap Indexing

• C. Chan, et al., Bitmap Index Design and Evaluation, in SIGMOD, 1998.

Hash Indexing

• X. Li, et al., Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, in EuroSys, 2014.
• S. Richter, et al., A Seven-Dimensional Analysis of Hashing Methods and Its Implications on Query Processing, in VLDB, 2015.

Approximate Indexing

• M. Athanassoulis, et al., BF-Tree: Approximate Tree Indexing, in VLDB, 2014.
• T. Kraska, et al., The Case for Learned Index Structures, in SIGMOD, 2018.
• H. Zhang, et al., SuRF: Practical Range Query Filtering with Fast Succinct Tries, in SIGMOD, 2018.

---

License

To the extent possible under law, Yingjun Wu has waived all copyright and related or neighboring rights to this work.