平衡2分木は基本だね

インデックスに対して、MongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しているらしいし、
Linux のプロセス・スケジューラーは、赤黒木を使っている

B TreeとB+ Treeの違い
https://christina04.hatenablog.com/entry/2017/05/17/190000