索引的作用是提高查询效率,其实现方式有很多种,常见的索引模型有哈希表、有序列表、搜索树等。
哈希表
- 一种以key-value键值对的方式存储数据的结构,通过指定的key可以找到对应的value。
- 哈希把值放在数组里,用一个哈希函数把key换算成一个确定位置,然后把value放在数组的这个位置。但是,多个key值经过哈希函数的换算,可能会出现同一个值,即哈希冲突,常见的解决办法是链地址法,即将所有的相同Hash值的key放在一个链表中,这样,无论有多少个冲突,都只是在当前位置给单链表增加节点。
- 适用于只有等值查询的场景,区间查询会很慢。
有序列表
- 支持等值查询和范围查询,但是更新数据的成本比较高。
- 适用于静态存储索引,比如保存的是2017年某个城市人口信息这类不会修改的数据。
树
1.二叉树:
- 每个节点的左儿子小于父节点,父节点小于右儿子。
- 查找、更新某个节点的时间复杂度都是O(log(N)),搜索效率最高。
2.B树(多叉树):
- 根节点至少有两个子节点,每个节点的子节点间,其大小都是从左到右递增。
3.B+树:
- B+树的叶子节点保存了父节点的所有键值和键值对应的数据,每个叶子节点的键值从小到大链接,但非叶子节点不保存键值对应的数据,这样使得B+树每个节点所能保存的键值大大增加;
- 由于B+树的非叶子节点只进行数据索引,不会存实际的键值对应的数据,所有的数据必须到叶子节点才能获取到,所以每次数据查询的次数都一样。
因为索引不止存在内存中,还要写在磁盘上,为了尽量少地读写磁盘,减少IO次数,所以尽管二叉树的效率很高,大多数数据库不会选择二叉树。
可以想象一下一棵 100 万节点的平衡二叉树,树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说,对于一个 100 万行的表,如果使用二叉树来存储,单独访问一个行可能需要 20 个 10 ms 的时间。
InnoDB使用B+树索引模型,所有数据都存储在B+树中,每一个索引对应一棵B+树。
以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。
结论:
InnoDB采用B+树结构,是因为B+树能够很好地配合磁盘的读写特性,减少单次查询的磁盘访问次数,降低IO、提升性能。