04索引原理:深入浅出索引(上)

分享:  

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

查询类型:

  • 等值查询;
  • 区间查询;

几种索引模型:

  • 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/