数据索引

索引常见模型

先介绍比较常见简单的数据索引：哈希表、有序数组、搜索树

哈希表

哈希表是一种以键值存储数据的结构，只用输入key就能找到value。

哈希表就是把key放在一个位置，把值经过计算均匀的分布在数组里，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

例如你需要在哈希值为2的链表里面新增一个值，直接在尾部添加就好了，但如果需要在里面查询某一个值，你得扫描里面所有的值，因为链表不是有序的。

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

有序数组

有序数组按数组递增的顺序排序，如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

搜索树

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。

二叉树搜索效率最高，但是数据存储不使用二叉树，因为索引可能还要写入磁盘中，因为是二叉，数据量大的情况下树高可能有几十，相当于几十个数据块，而磁盘读取一个数据块需要花费10ms，相对来说查询太慢了。

树可以有二叉也可以有多叉，每个节点下面有多个儿子，N叉树用很低的树高，存储庞大的数据，减少对磁盘的访问，被广泛用于数据库中。

B+树类似于多叉树，不过可以在最后的子节点用双向链表连了起来，比如我只需要找到8-10这个区间，然后通过8往后面遍历找到后面的9。

这样它完美地支持了我们提的三个需求：快速查找值，区间，顺序逆序查找。

索引维护

在插入新值的时候，需要往后挪动位置，但是刚刚数据已经满了，只能开启新的一页，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂，会影响性能。

如果是以自增 id 作为主键，由于新插入的表中生成的 id 比索引中所有的值都大，所以它要么合到已存在的节点(元素个数未满)中，要么放入新建的节点中(如下图示)所以如果是以自增 id 作为主键，就不存在页分裂的问题了。

也会有页合并的情况，删掉了两个数据，数据分散在两个不同的节点上，可能造成两次 IO 读，势必会影响查找效率! 那什么时候会发生页合并呢，我们可以定个阈值，比如对于 N 叉树来说，当节点的个数小于 N/2 的时候就应该和附近的节点合并，不过需要注意的是合并后节点里的元素大小可能会超过 N，造成页分裂，需要再对父节点等进行调整以让它满足 N 叉树的条件。

假如有很长的身份证，还是用ID作为主键呢，答案肯定是用ID，因为索引越长占用空间越大。