数据库系列2-索引

可以实现索引的数据结构有多种，包括哈希表、有序数组和搜索树等。

哈希表

key-value对，当做索引存在的缺陷：

a.只能等值查询，不支持范围查询

b.存在hash冲突，严重的情况下退化成链表

有序数组

有序数组能很好地支持等值查询和范围查询，但有序数组的更新成本高（比如在下标i处插入一条新数据，i后面的数据都要向后挪移），根据这个特性，很适合作为静态数据的索引实现

搜索树

一般来讲，搜索树特指二叉搜索树，是有序的，按照中序遍历得到一个递增序列。因为任何一个节点最多只有两个子节点，所以树的高度随节点数量增大而增高，height >= log(n)。树的高度代表读取磁盘的次数，所以为了减少读磁盘的次数，想办法降低树的高度，只能增大子节点数量。MySQL的索引用的数据结构便是B+树。B+树作为索引在访问磁盘数据中能大大提高效率，所以B+树不仅用于数据库的索引，也适用于各种文件系统。

所以先去了解下B树和B+树。

B树的的增删改查操作，添加数据时，难点在于节点的分裂，将中间key加入父节点。如果父节点的key数量也超过了，递归分裂父节点。

在MySQL中，每一个索引就是一颗B+树，那么MySQL的索引利用B+树是怎么实现索引的。数据存放在叶子节点

这里其实更像跳表，叶子层有全量的数据，而非叶子层是部分的数据用于分块的，

按照叶子节点里存的数据，索引分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据（其实是这行数据在磁盘上的block相关地址），主键索引也成为聚簇索引。（非得搞这么高大上的名字。。。）

非主键索引的叶子节点存的是主键的值，非主键索引也成为二级索引。

查询数据一定是通过主键索引去查的，因为数据存在磁盘上的哪个位置只有主键索引里有。所以主键天然就是有索引的。如果不显示指定表的主键，则MySQL默认会有一个创建一个row_id作为隐式的主键。

当根据非主键索引查询到符合条件的主键后，再去主键索引里找其对应的数据。这个过程叫做回表。

这里解释一个问题，为什么主键索引要用自增数字作为主键，因为自增，每次都是追加，不会在主键索引中存在插入的场景，尽可能在新增数据过程分裂节点。另一方面，从存储方面来讲，整形是4个字节，长整型是8个字节。占用空间更少。

如果在一次查询查询中，查询的字段刚好都在联合索引的字段里，这时直接查询一次二级索引就可以了，不用再去查主键索引（找出整行数据，拿到需要的字段）。这就是索引覆盖，可以作为一种优化方案。

联合索引和最左匹配原则

MySQL对联合索引的存储是根据索引定义中字段的顺序，将所有字段”拼接成一个字符串”（可以先这么简单理解，具体的实现方案暂且不管）。所以，当只按照这个联合索引的第一个字段查询时，依旧可以走这个索引，效果跟第一个字段建立的单独索引的效果一样。因此，在定义联合索引的字段顺序时，谁放在前，看哪个字段更需要单独的索引，即尽可能避免再对联合索引中的字段单独再建索引。

因为索引是有序的，对于联合索引，就是第一个字段是有序的，所以根据联合索引中的非第一个字段过滤数据时，就只能通过主键索引，全表逐行过滤

索引的序列化

当持久化索引时，怎么序列化内存中的索引数据，关键点在于怎么记录key之间的位置关系。参考mapdb