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
• In-Memory Hash Indexing
• NVM-based Hash Indexing
• SSD-based Hash Indexing
• Bitmap 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.
• J. Arulraj, et al,. BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory, in PVLDB, 2018.
• T. Wang, et al,. Easy Lock-Free Indexing in Non-Volatile Memory, in ICDE, 2018.
• D. Hwang, et al,. Endurable Transient Inconsistency in Byte-Addressable Persistent B+-Tree, in FAST, 2018.

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.

In-Memory 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.

NVM-Based Hash Indexing

• P. Zuo, et al., Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory, in OSDI, 2018.
• M. Nam, et al., Write-Optimized Dynamic Hashing for Persistent Memory, in FAST, 2019.
• B. Lu, et al,. Scalable Hashing on Persistent Memory, in VLDB, 2020.

SSD-Based Hash Indexing

• P. Jin, et al,. SAL-Hashing: A Self-Adaptive Linear Hashing Index for SSDs, in TKDE, 2020.

Bitmap Indexing

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

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.
• J. Ding, et al., ALEX: an updatable adaptive learned index, in SIGMOD, 2020.
• V. Nathan, et al,. Learning multi-dimensional indexes, in SIGMOD, 2020.
• C. Tang, et al,. XIndex: A Scalable Learned Index for Multicore Data Storage, in, PPoPP, 2020.

---

License

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