关系型数据库的索引被用来加速数据的查找。
使用什么数据结构？
对比：
- Hash Table：查单个数据时快；不方便落盘；数据多时内存可能不够用；不支持范围查询
- 平衡树：支持范围查询；更新和查询性能好 O(log n)；不方便落盘
- B+Tree：支持范围查询；适合落盘；更新和查询性能好；本质上是以更多的分支来减少层高，从而使读写性能高
主流的 RDBMS 都使用 B+Tree。
操作的考虑点：
- 插入数据：页内数据可能被挪动；单页可能满，会有页分裂过程
- 删除数据：页内容稀疏时会合并
- 使用自增 ID 做插入操作时，key 的值总是增加，数据不需要挪动、页分裂时性能也好