索引模型

什么是数据库索引

索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。

• 索引的出现其实就是为了提高数据查询的效率。

数据库索引模型

哈希表

哈希表是一种以键key/value存储数据的结构，只要输入key，就可以找到其对应的值Value。

• 哈希表将值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。
• 多个key值经过哈希函数的换算，会出现同一个值的情况，处理这种情况的一种方法是拉出一个链表。

哈希表的示例：

• 该表为身份证信息和姓名的表，需要根据身份证号查找对应的名字。
• User2和User4根据身份证号算出来的值都是N；假设要查ID_card_n2对应的名字是什么，首先将ID_card_n2通过哈希函数算出N，然后按顺序遍历，找到User2。

哈希表中的值并不是递增的，这样做的好处是增加新key时速度会很快，只需要往后追加；但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

• 哈希表这种结构适用于只有等值查询的场景，比如 Memcached及其他一些NoSQL引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能都非常优秀。

有序数组的示例：

• 假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。
• 如果查询ID_card_n2对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。
• 如果查询查身份证号在[ID_card_X, ID_card_Y]区间的User，可以先用二分法找到ID_card_X（如果不存在ID_card_X，就找到大于ID_card_X的第一个 User），然后向右遍历，直到查到第一个大于ID_card_Y的身份证号，退出循环。

有序数组在需要更新数据的时候，需要在中间插入值，则必须挪动后面所有的记录，效率很差。

• 有序数组索引只适用于静态存储引擎。

二叉树

二叉树的示例：

• 二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。
• 如果查询ID_card_n2，按照图中的搜索顺序就是按照UserA -> UserC -> UserF -> User2这个路径得到；这个时间复杂度是 O(log(N))，为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树，为了做这个保证，更新的时间复杂度也是 O(log(N))。

二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。

• 索引不止存在内存中，还要写到磁盘上；如果一棵100万节点的平衡二叉树，树高20，一次查询可能需要访问20个数据块，在机械硬盘时代，从磁盘随机读一个数据块需要10ms 左右的寻址时间。也就是说，对于一个100万行的表，如果使用二叉树来存储，单独访问一个行可能需要20个10ms的时间，效率非常差。
• 为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块，因此就需要使用”N叉”树；这里，”N叉树中的”N”取决于数据块的大小；以InnoDB的一个整数字段索引为例，这个N差不多是1200，这棵树高是4的时候，就可以存1200的3次方个值，这已经17亿了；考虑到树根的数据块总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。