Abstract
Different uses for read-optimized B-trees and write-optimized LSM-trees.
- Apple HFS Plus Volume Format; https://developer.apple.com/legacy/library/technotes/tn/tn1150.html#BTreesGoogle Scholar
- Bloom, B.H. Space/time trade-offs in hash coding with allowable errors, Commun. ACM 13, 7 (1970), 422--426 Google ScholarDigital Library
- Comer, D. The ubiquitous B-tree. Computing Surveys 11, 2 (1979); 121--137; https://bit.ly/2w2Ms01 Google ScholarDigital Library
- Data Systems Laboratory at Harvard. The RUM Conjecture; http://daslab.seas.harvard.edu/rum-conjecture/.Google Scholar
- Graefe, G. Modern B-tree techniques. Foundations and Trends in Databases 3, 4 (2011), 203--402; https://bit.ly/2IbTB36 Google ScholarDigital Library
- Mathur, A., Cao, M., Bhattacharya, S., Dilger, A., Tomas, A. and Vivier, L. The new ext4 filesystem: Current status and future plans. In Proceedings of the Linux Symposium. Ottawa, Canada, 2007; https://bit.ly/2HMJiyWGoogle Scholar
- MySQL 5.7 Reference Manual. The physical structure of an InnoDB index; https://dev.mysql.com/doc/refman/5.7/en/innodb-physical-structure.html.Google Scholar
- O'Neil, P., Cheng, E., Gawlick, D. and O'Neil, E. The log-structured merge-tree. Acta Informatica 33, 4 (1996), 351--385; https://bit.ly/2HJ2UYO Google ScholarDigital Library
- Pelkonen, T., Franklin, S., Teller, J., Cavallaro, P., Huang, Q., Meza, J. and Veeraraghavan, K. Gorilla: A fast, scalable, in-memory time series database. In Proceedings of the VLDB Endowment 8, 12 (2015): 1816--1827; http://www.vldb.org/pvldb/vol8/p1816-teller.pdf. Google ScholarDigital Library
- Suzuki, H. The internals of PostgreSQL, 2015-2018; http://www.interdb.jp/pg/pgsql01.html.Google Scholar
Index Terms
- Algorithms behind modern storage systems
Recommendations
Algorithms Behind Modern Storage Systems: Different uses for read-optimized B-trees and write-optimized LSM-trees
ConsistencyThis article takes a closer look at two storage system design approaches used in a majority of modern databases (read-optimized B-trees and write-optimized LSM (log-structured merge)-trees) and describes their use cases and tradeoffs.
On the parallelism of I/O scheduling algorithms in MEMS-based large storage systems
MEMS-based storage is being developed as a new storage media that has several salient characteristics such as high-parallelism, high density, and low-power consumption. Because physical structures of MEMS-based storage is different from those of hard ...
Comments