04索引原理：深入浅出索引（上）

Posted 2021-04-17 16:00 +0800 by ZhangJie ‐ 1 min read

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。直接在几百页的书找一个关键词可能要找很久，但是通过附录中先通过首字母找到对应的关键词，再通过关键词对应页码找到书中对应页、对应内容，就会比较快。查词典、查电话本，都是类似的思想。

查询类型：

• 等值查询；
• 区间查询；

几种索引模型：

• hash

  这种只适合等值查询，接近O(1)的时间复杂度，不适合范围查询（比如key介于[k1,k2]之间的就得全量扫描了）。这类存储，主要有memcached及其他一些nosql存储；

• 有序数组

  在等值查询、范围查询场景中，性能都比较好，基本可以在O(log(n))时间复杂度内搞定。当然数据有序、没有重复等情况下，平均复杂度要坏一点。但是考虑到插入的场景，插入点位置及以后的数据要移动的，代价比较高。

  有序数组，只适用于静态存储引擎，不怎么变化的那种存储。

• 搜索树

  根据对树中索引节点key的数量以及对树的高度的不同，可以分为好几种，比较常见的有二叉搜索树、二叉平衡树、红黑树，这些都是二叉的，时间复杂度基本都是O(log(n))，但是考虑到平均时间复杂度二叉平衡树是最好的，但是它的插入操作涉及到大量的树调整步骤，开销较大，普通二叉搜索树的话又有可能退化为一个单支的链表，查询性能退化为O(n)。红黑树是一个比较好的选择，使用也比较广，它通过施加一些约束限制了左、右子树高度不会成为另一个的两倍，这比二叉平衡树左右子树高度差最多为1可松多了，减轻了树调整的开销。红黑树是用的比较多的。

  树的搜索效率取决于树的高度，如果树高度很高，那么查询效率自然就会比较低。考虑到机械硬盘随机访问慢的特性，每个索引节点都要取机械硬盘里面去加载的，这个很慢的。数据库设计出来是要存储大量数据的，索引关键字区分度再高，二叉树出度太低，树还是会很高的，这对存储大量数据（几千万上亿）的数据库系统来说，二叉树有点吃不消，所以B树、B+树出现了。

  试想下，二叉树的情况下，节点多了之后，树高度会很高的，每个索引节点都可能存储在机械硬盘上离散的位置，读取每个索引节点会很耗时的。

  B树是m叉树，但是B树中的非叶子节点既可能是索引节点，也可能是数据节点，数据节点之间没有形成一个有序链表，没有充分考虑到机械硬盘顺序读取效率高的特点，B+树考虑到了，所有非叶子节点都是索引节点，所有，叶子节点均为数据节点，且构成了一个有序的链表，正好能解决机械硬盘随机访问慢的问题，也能利用硬盘顺序读取快的优势。

m叉树中的这个m应该多大呢？这个取决于数据块的大小，以InnoDB的一个整数字段索引为例，这个N差不多是1200。树高4层的时候，就差不多可以存储17亿条数据了。

ps：类似的怎么计算呢？

学习下怎么计算的：https://www.programmersought.com/article/65874297377/

现代机械硬盘最大不知道多少，innodb里面定义的是索引中指针大小是6个字节，意味着2^(6*8)/2^40=256TB，这里的指针大小表示的是数据在表空间中的偏移量，可以理解成可以寻址256TB的硬盘空间？

innodb默认的pagesize是16KB，ok！

• 先算一个索引可以存多少指针：假定我们用bigint作为主键，8个字节，指针6字节，那一个索引节点可以存储16KB/14B=1170个关键字和指针。
• 再算一个叶子节点可以存多少记录：聚集索引里面叶子节点中，索引关键字是数据记录的一部分，至少大于8个字节了，我们就假定一行记录大约么为1KB吧。那么一个叶子节点可以存储记录数量为16KB/1KB=16。

现在我们笼统算法下：

• 假如树最大高度为2，那么就是根节点指针数量*每个叶子节点记录数量，可以存储1170x16=18720

• 假如数最大高度为3，那么就是1170^2*16=21902400=2190w

• 假如数最大高度为4，那么就是1170^3*16=25625808000=256亿

实际情况一般3层就可以满足绝大部分场景使用了，数据量大的话，也极少有业务会超过4层。所以存储很多的数据，查询效率也基本上是有保证的。

每次查询索引节点，都代表了一次磁盘IO，所以通过主键索引查询，会比借助其他辅助索引查询、再回表的方式要快一些。

指针6个字节，意味着可以寻址的索引地址空间很大的，256TB，哪有这么大的内存，这个东西也可以理解成磁盘上索引的偏移量，256TB的硬盘。

但是看得出来，索引可能也很大，不一定能完全在硬盘中存储的下，也是按需加载的！

ps：为什么要用自增id作为主键，有什么好处，主要是为了避免插入时页分裂，b+树调整导致的效率低下：https://zhuanlan.zhihu.com/p/71022670

ps：innodb b+tree索引结构：https://www.programmersought.com/article/1411118316/