第五章 创建高性能的索引-读书笔记

在MySQL中,分为引擎层和服务器层,索引是在存储引擎层实现的。不同的存储引擎的索引的工作方式并不一样。 索引的优点:

  • 索引大大减少了服务器需要扫描的数据量。
  • 索引可以帮助服务器避免排序和临时表。
  • 索引可以将随机IO变为顺序IO。 三星索引
  • 一星 : 将相关的记录放到一起
  • 二星 : 索引中的数据顺序和查找的顺序一致
  • 三星 : 索引中的列包含了查询中需要的全部列,则获得了三星。

MySQL 支持的索引类型

MyISAM vs InnoDB

  • MyISAM 使用前缀压缩技术使得索引更小,但InnoDB 则按照原数据格式进行存储。
  • MyISAM 使用数据的物理位置引用被索引的行,而InnoDB 根据主键引用被索引的行。
  • MyISAM 按照数据插入的顺序存储在磁盘上。
  • MyISAM 的主键索引和二级索引没有本质的区别,InnoDB的主键索引和二级索引非常不同,InnoDB的主键索引中每个叶子结点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有剩余列。二级索引的叶子结点存储的不是行指针而是主键的值。使用主键值替换行指针会让二级索引占用更多的空间,带来的好处是移动行时,不用更新这个行的主键值。

    B-Tree 索引(B+Tree)

    B-Tree的特征:

  • B-Tree的整体目标是降低【网络访问的次数/seek 磁盘】的次数。
  • B-Tree的高度决定了在访问数据时,seek的最大的次数。
  • B-Tree的高度:logm(n) [log base m of n]

所以随机磁盘访问的次数不会超过 logm(n). 所以,B-Tree是针对当数据无法完全放入内存中时,为了尽可能的降低磁盘访问次数而出现的一种优化的算法。

B-Tree 分支因子 m:

  1. 节点中所有key 都是有序的。
  2. 每一个节点包含了不超过m - 1个节点。(m - 1 keys have m children.)
  3. 每一个非叶子节点包含了最多 m个children。所以,分支因子为m的b-tree就像一个m叉树。
    • a root node can be a leaf or have [2, m] children.
    • Each non-root, internal node has [ceil(m/2), m] children.
  4. 每一个叶子页到根的距离相同,也就是所有节点都在同一层上。

为什么B-Tree 索引能够加快访问速度? 使用了索引,存储引擎不再需要进行全表扫描来获取需要的数据,而是从索引的根结点进行搜索。查找的方式类似二叉树,这些指针定义了子节点页中值的上限/下限。 截屏2022-07-01 18.27.00 叶子结点比较特别,叶子结点中的指针指向的是被索引的数据,而不是其他的结点页。 note:

InnoDB 存储引擎的最小存储单元是页(16kb),页可以用于存放数据(叶子节点)也可以用于存放键值 + 指针(非叶子结点),在 B+ 树中叶子节点存放数据,非叶子节点存放键值 + 指针。 索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中,进而在去数据页中查找到需要的数据;

通常一棵 B+ 树可以存放多少行数据?

先假设树的高度为2,即存在一个根结点和若干个叶子结点,那么,这个B+Tree可以存放的总记录数为 根节点指针数 * 单个叶子节点记录行数 假设行记录大小为 1kb,所以:单个叶子节点(页)中的记录数 =16K/1K=16 那么,非叶子结点能存多少指针? 假设主键为bigint类型,占用8个字节,而指针大小在 InnoDB 源码中设置为 6 字节,这样一共 14 字节,我们一个页中能存放多少这样的单元,其实就代表有多少指针,即 16384/14=1170 那么可以算出一棵高度为 2 的 B+ 树,能存放 1170*16=18720 条这样的数据记录。 根据同样的原理我们可以算出一个高度为 3 的 B+ 树可以存放: 1170*1170*16=21902400 条(大概2千万)这样的记录。 所以在 InnoDB 中 B+ 树高度一般为 1-3 层,它就能满足千万级的数据存储。 在查找数据时一次页的查找代表一次 IO,所以通过主键索引查询通常只需要 1~3 次 IO 操作即可查找到数据。 为什么 MySQL 的索引要使用 B+ 树而不是其它树形结构? B+树其实是基于B树结构做的优化。

  • 非叶子结点中只保存键的信息,可以将更多的键压入到页中,让树具有更高的分支因子,也就是logm(n)中的m,这样,树的高度就能够降低,高度直接决定了磁盘随机扫描的次数。
  • 在叶子结点中,每个叶子页面可能会向左和向右引用其他同级的兄弟页,这样可以顺序扫描,而不用跳回到父页面。

可以使用B-Tree 索引的查询类型?

  • 全值匹配
    • 指的是和索引的所有列匹配
  • 匹配最左前缀
  • 匹配列前缀
  • 匹配范围值
  • 精确匹配某一列,并范围匹配另一列
  • 只访问索引的查询 - 覆盖索引

  • 索引的限制:
    • 如果不是按照索引的最左列开始查找,则无法使用索引。
    • 不能跳过索引中的列。
    • 如果查询中,有某个列使用了范围查询,那么其右边的所有列都无法使用索引优化查找。

高性能索引的策略

三星索引设计策略。 额外的策略:

  1. 中的列必须是独立的,不能是表达式中的一部分,也不能是函数的参数。
  2. 前缀索引和索引选择性。
    1. 针对特别长的字符串,可以基于字符串的prefix 做索引,基于区分度选择子串的长度。 后缀索引的场景,翻转字符串,取前缀。
  3. 多列索引
    1. index merge 有时候是一种优化的结果,更多的是说你这个索引建的不好。
  4. 选择合适的索引列的顺序
    1. 选择合适的索引列顺序,经验法则:选择性最高的列放到索引的最前列(不考虑排序和分组)。 优先考虑避免随机IO 和避免排序。
  5. 在InnoDB中按主键顺序插入行
  6. 使用索引扫描做排序
  7. 避免冗余和重复索引
    1. pt-duplicate-key-checker 为什么不推荐使用UUID 作为主键?
      • 写入目标页可能已经刷到磁盘上并从缓存中移除,或者是还没有被加载到缓存中,InnoDB 在插入之前不得不先找到并从磁盘读取目标页到内存中,这将导致大量的随机IO。
      • 因为写入时乱序的,InnoDB 不得不频繁的做业分裂操作,以便为新的行分配空间。页的分裂会导致移动大量的数据,一次插入最少需要修改三个页,而不是一个页。
      • 由于页分裂,页会变的稀疏,产生磁盘碎片。

可以通过Optimize table 来重建表并优化表的填充。
使用InnoDB时,应该尽可能地按照主键顺序插入数据,并且尽可能地使用单调增加的聚簇键的值来插入新行。

覆盖索引的优势

  • 索引的数据远少于数据行大小,所以如果只需要读索引,那么就会减少极大的访问量。【数据拷贝少了,所以比数据少,更容易全部放入内存】
  • Innodb 不需要回表。

覆盖索引必须存储索引列的值,而hash索引、空间索引和全文索引都不存储列的值,MySQL 只能使用B-Tree作为覆盖索引。

参考:https://zhuanlan.zhihu.com/p/86137284