04 | 深入浅出索引（上）

索引的常见模型

索引的出现就是为了提高数据查询的效率，就像书的目录一样。实现索引的方式有很多种，这里也引入了索引模型的概念。

可以用于提高读写效率的数据结构有很多种，比较常见的三种就是哈希表、有序数组和搜索树。

哈希表：以键值存储数据的结构，只需要输入待查找的值即key，就可以找到对应的值value。哈希的思路是把值放到数组里，用哈希函数把key换算成下标，然后把value放到这个位置。多个key值经过哈希函数的换算，会出现同一个值的情况，处理方法之一就是拉出一个链表。只适用于等值查询的场景。

有序数组：等值查询和范围查询中都有很好的性能，其中等值查询可以使用二分法查找，时间复杂度是O(logn)。但是更新的成本很高，因为往中间插入一个记录就必须挪动后面所有记录。所以有序数组索引只适用于静态存储引擎

二叉搜索树：每个节点的左儿子小于父节点，父节点小于右儿子。搜索的时间复杂度是O(logn)。为了维持这个查询复杂度，需要保持这棵树是平衡二叉树，所以更新的时间复杂度也是O(logn)。

多叉树是每个节点有多个儿子，儿子之间的大小保证从左到右递增。

二叉树的搜索效率最高，但是大多数的数据库存储不适用二叉树，因为索引不止在内存里，还在磁盘上。一棵100万节点的平衡二叉树，树高20，依次查询可能访问20个数据块，从磁盘随机读一个数据块需要10ms左右的寻址时间，那么单独访问一行需要200ms时间，效率很低。为了让一个查询尽可能少得读磁盘，