A Review on Binary Search Trees and Red-Black Trees for Database Indexing: Comparative Analysis with Production Database Systems and A Demonstrative Case Study

Database indexing is fundamental to efficient information retrieval in educational, enterprise, and low-latency systems. This paper presents a structured literature review comparing Binary Search Trees (BST), Red-Black Trees (RBT), and production database index structures—particularly B-trees and B+ trees—used in SQLite, MySQL, PostgreSQL, Oracle, and MongoDB. Following guidelines for systematic literature reviews in software engineering, 68 publications were screened from IEEE Xplore, ACM Digital Library, ScienceDirect, and official database documentation (1972–2026); 29 sources were selected for qualitative synthesis. The review explains algorithmic properties, disk-scale indexing requirements, and application-specific structure selection. A demonstrative case study—the Smart Student Record Management Portal—illustrates how synchronized in-memory BST and RBT indexes can be layered over SQLite for educational visualization. Experiments across five query categories, three modest dataset sizes (500–2,000 records), and three insertion orders (sorted, random, reverse) were conducted on a single laptop in single-threaded Python; they show that unbalanced BST height grows linearly under sorted insertion (up to 565 at n=1,106) while RBT remains near-logarithmic (height 10–18). SQLite indexed lookups completed in 40–47 µs under these conditions. These timings measure educational in-memory tree traversal and an embedded SQLite baseline; they are not a direct benchmark of production database indexing, which additionally depends on persistence, I/O, concurrency, caching, and the query optimizer. The paper concludes that BST/RBT are valuable for pedagogy and in-memory ordered maps, while disk-scale databases require multi-way B+ trees with persistence, concurrency, and I/O-aware engineering beyond asymptotic complexity alone.

Binary Search Tree, Red-Black Tree, Database Indexing, B+ Tree, Literature Review, Student Record Management, Low-Latency Systems

1. Bayer, R., & McCreight, E. (1972). Organization and maintenance of large ordered indexes. Acta Informatica, 1(3), 173-189. https://doi.org/10.1007/BF00288685 [Google Scholar] [Crossref]

2. Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., & Gruber, R. E. (2008). Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 26(2), 1-26. https://doi.org/10.1145/1365815.1365816 [Google Scholar] [Crossref]

3. Comer, D. (1979). The ubiquitous B-tree. ACM Computing Surveys, 11(2), 121-137. https://doi.org/10.1145/356770.356776 [Google Scholar] [Crossref]

4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press. [Google Scholar] [Crossref]

5. Elmasri, R., & Navathe, S. B. (2016). Fundamentals of database systems (7th ed.). Pearson. [Google Scholar] [Crossref]

6. Graefe, G. (2011). Modern B-tree techniques. Foundations and Trends in Databases, 3(4), 203-402. https://doi.org/10.1561/1900000028 [Google Scholar] [Crossref]

7. Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data structures and algorithms in Python. John Wiley & Sons. [Google Scholar] [Crossref]

8. Guibas, L. J., & Sedgewick, R. (1978). A dichromatic framework for balanced trees. Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 8-21. [Google Scholar] [Crossref]

9. Kitchenham, B., & Charters, S. (2007). Guidelines for performing systematic literature reviews in software engineering (EBSE Technical Report EBSE-2007-01). Keele University. [Google Scholar] [Crossref]

10. Lehman, P. L., & Yao, S. B. (1981). Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems, 6(4), 650-670. https://doi.org/10.1145/319628.319663 [Google Scholar] [Crossref]

11. Lomet, D. B. (2001). Evolution of the B-tree. ACM SIGMOD Record, 30(3), 11-18. https://doi.org/10.1145/582162.582165 [Google Scholar] [Crossref]

12. MongoDB Inc. (2024). WiredTiger storage engine. https://www.mongodb.com/docs/manual/wiredtiger/ [Google Scholar] [Crossref]

13. MySQL AB. (2024). MySQL 8.0 reference manual: InnoDB index types. https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html [Google Scholar] [Crossref]

14. O'Neil, P., Cheng, E., Gawlick, D., & O'Neil, E. (1996). The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4), 351-385. https://doi.org/10.1007/s002780050048 [Google Scholar] [Crossref]

15. Oracle Corporation. (2024). Oracle Database reference: B-tree indexes. https://docs.oracle.com/en/database/oracle/oracle-database/19/cncpt/ [Google Scholar] [Crossref]

16. Page, M. J., McKenzie, J. E., Bossuyt, P. M., Boutron, I., Hoffmann, T. C., Mulrow, C. D., et al. (2021). The PRISMA 2020 statement. BMJ, 372, n71. https://doi.org/10.1136/bmj.n71 [Google Scholar] [Crossref]

17. PostgreSQL Global Development Group. (2024). PostgreSQL 16 documentation: Indexes. https://www.postgresql.org/docs/16/indexes.html [Google Scholar] [Crossref]

18. Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676. https://doi.org/10.1145/78973.78977 [Google Scholar] [Crossref]

19. Ramakrishnan, R., & Gehrke, J. (2003). Database management systems (3rd ed.). McGraw-Hill. [Google Scholar] [Crossref]

20. Rao, D., & Ross, K. A. (1999). Cache conscious indexing for decision-support in main memory. Proceedings of VLDB, 78-89. [Google Scholar] [Crossref]

21. Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652-686. https://doi.org/10.1145/3821.3835 [Google Scholar] [Crossref]

22. SQLite Consortium. (2024). SQLite database file format. https://www.sqlite.org/fileformat2.html [Google Scholar] [Crossref]

23. Stonebraker, M., & Hellerstein, J. M. (2005). Readings in database systems (4th ed.). MIT Press. [Google Scholar] [Crossref]

24. Tanenbaum, A. S., & Bos, H. (2015). Modern operating systems (4th ed.). Pearson. [Google Scholar] [Crossref]

25. Weiss, M. A. (2014). Data structures and algorithm analysis in C++ (4th ed.). Pearson. [Google Scholar] [Crossref]

26. Winand, M. (2012). SQL performance explained. Markus Winand. [Google Scholar] [Crossref]

27. Zobel, J., & Moffat, A. (2006). Inverted files for text search engines. ACM Computing Surveys, 38(2), 1-56. https://doi.org/10.1145/1132956.1132959 [Google Scholar] [Crossref]

28. Kumar, A., Singh, R., & Patel, V. (2023). Web-based student information management systems: A systematic review. IJACSA, 14(5), 112-121. https://doi.org/10.14569/IJACSA.2023.0140513 [Google Scholar] [Crossref]

29. Molyneaux, I. (2009). The art of application performance testing. O'Reilly Media. [Google Scholar] [Crossref]

• What the Desert Fathers Teach Data Scientists: Ancient Ascetic Principles for Ethical Machine-Learning Practice
• Comparative Analysis of Some Machine Learning Algorithms for the Classification of Ransomware
• Comparative Performance Analysis of Some Priority Queue Variants in Dijkstra’s Algorithm
• Transfer Learning in Detecting E-Assessment Malpractice from a Proctored Video Recordings.
• Dual-Modal Detection of Parkinson’s Disease: A Clinical Framework and Deep Learning Approach Using NeuroParkNet