数据库索引

文件索引允许我们能够以较快地速度查询到目标文件的存储地址，其最典型的应用场景即是MySQL等关系型数据库。在数据库中,数据本身是存储在文件里的，而为了能够快速定位到某张表里的某条记录进行查询和修改，我们需要将这些数据以一定的数据结构进行存储，这个数据结构就是我们说的索引。可以实现增删改查的数据结构非常多，包括：哈希表、二叉搜索树、AVL、红黑树、B树、B+树等，这些都是可以作为索引的候选数据结构。

• 有序数组：按顺序存储。查询用二分法就可以快速查询，时间复杂度是：O(log(N))。查询效率高，更新效率低（涉及到移位）。在等值查询和范围查询场景中的性能就都非常优秀。有序数组索引只适用于静态存储引擎。
• 哈希表：一种以KV存储数据的结构，哈希的思路是把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。哈希冲突的处理办法是使用链表。哈希表适用只有等值查询的场景。
• 二叉搜索树：每个节点的左儿子小于父节点，右儿子大于父节点。查询时间复杂度O(log(N))，更新时间复杂度O(log(N))。数据库存储大多不适用二叉树，因为树高过高，会适用N叉树

可以实现增删改查的数据结构非常多，包括：哈希表、二叉搜索树、AVL、红黑树、B树、B+树等，这些都是可以作为索引的候选数据结构。

实际应用中，我们往往使用B+树或者LSM来替代二叉查找树或者红黑树来构建索引系统，并且充分利用虚拟存储管理 一节中介绍过的局部性原理、磁盘预读与页缓存等概念。

Links

• https://neway6655.github.io/elasticsearch/2015/09/11/elasticsearch-study-notes.html#elasticsearch%E6%98%AF%E5%A6%82%E4%BD%95%E5%81%9A%E5%88%B0%E5%BF%AB%E9%80%9F%E7%B4%A2%E5%BC%95%E7%9A%84