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.
- 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
- 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.
- 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.
- Y. Li, et al., Tree Indexing on Solid State Drives, in VLDB, 2010.
- 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.
- 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.
- 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.
- 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.
- P. Jin, et al,. SAL-Hashing: A Self-Adaptive Linear Hashing Index for SSDs, in TKDE, 2020.
- C. Chan, et al., Bitmap Index Design and Evaluation, in SIGMOD, 1998.
- 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.
To the extent possible under law, Yingjun Wu has waived all copyright and related or neighboring rights to this work.