索引
数据库索引
文件索引允许我们能够以较快地速度查询到目标文件的存储地址，其最典型的应用场景即是 MySQL 等关系型数据库。在数据库中,数据本身是存储在文件里的，而为了能够快速定位到某张表里的某条记录进行查询和修改，我们需要将这些数据以一定的数据结构进行存储，这个数据结构就是我们说的索引。可以实现增删改查的数据结构非常多，包括：哈希表、二叉搜索树、AVL、红黑树、B 树、B+树等，这些都是可以作为索引的候选数据结构。
- 有序数组：按顺序存储。查询用二分法就可以快速查询，时间复杂度是：O(log(N))。查询效率高，更新效率低（涉及到移位）。在等值查询和范围查询场景中的性能就都非常优秀。有序数组索引只适用于静态存储引擎。
- 哈希表：一种以 KV 存储数据的结构，哈希的思路是把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。哈希冲突的处理办法是使用链表。哈希表适用只有等值查询的场景。
- 二叉搜索树：每个节点的左儿子小于父节点，右儿子大于父节点。查询时间复杂度 O(log(N))，更新时间复杂度 O(log(N))。数据库存储大多不适用二叉树，因为树高过高，会适用 N 叉树
可以实现增删改查的数据结构非常多，包括：哈希表、二叉搜索树、AVL、红黑树、B 树、B+树等，这些都是可以作为索引的候选数据结构。
实际应用中，我们往往使用 B+ 树或者 LSM 来替代二叉查找树或者红黑树来构建索引系统，并且充分利用虚拟存储管理 一节中介绍过的局部性原理、磁盘预读与页缓存等概念。