02
B - 树
m 阶 B - 树也称作 (ceil(m), m) 树, 如 (2,3) 树, 称为 3 阶 B 树,(2,4)树称为 4 阶 B 树
如下为 4 阶 B - 树, 每个节点至少含有 2 个分支, 至多含有 4 个分支, 也就是说, 每个节点至少含有 1 个数据节点, 至多含有 3 个数据节点
03
B + 树
B + 树和 m 阶的 B - 树的差异在于:
内节点(非叶子节点), 只用来索引;
所有的外节点(叶子结点) 中包含了:
1) 全部关键字的信息
2) 指向含这些关键字记录的指针
3) 外节点(叶子结点) 本身依关键字的大小自小而大顺序链接
如下所示, 所有节点都有 key 域; 叶节点的数据域上才真正存储着数据, 而非叶节点的数据域只保存多个指针
04
为什么是 B + 树? 而不是红黑树
为什么 MySQL 选择了 B + 树, 而不是红黑树作为数据库的索引呢?
B+Tree 中一次检索最多需要 h-1 次 I/O(根节点常驻内存), 树的高度为 O(logdN)一般实际应用中, 一个节点的分支数 (出度 d) 是非常大的数字 (通常大于 100), 因此树的高度会非常小(通常不超过 3) 索引设计为 B + 数据结构, 一次检索所需要的 I/O 次数就会很小我们又知道, 访问内存的延迟大约为 ns 级, 而访问磁盘的延迟为 ms 级, 这相当于, 访问内存延迟如果 1 天的话, 访问外存延迟需要 2000 年
根据磁盘预读原理, B + 树将一个节点的大小设为等于一个页, 这样每个节点只需要一次 I/O 就可以完全载入每次新建节点时, 直接申请一个页的空间, 这样就保证一个节点物理上也存储在一个页里
而红黑树这种结构, h 明显要深的多并且, 红黑树中逻辑上很近的节点 (父子) 物理上可能很远, 无法利用局部性
综上, B + 树更适合做索引
05
MyISAM 和 InnoDB 存储引擎
在 MySQL 中, 不同存储引擎对索引的实现方式是不同的, 总结下 MyISAM 和 InnoDB 两个存储引擎的索引实现方式
MyISAM 引擎使用 B+Tree 作为索引结构, 叶节点的 data 域存放的是数据记录的地址
第一列作为主索引的 MyISAM 引擎存储结构, 要求主索引取值唯一
虽然 InnoDB 也使用 B+Tree 作为索引结构, 但具体实现方式却与 MyISAM 不同 InnoDB 的叶子节点的数据域保存了完整的数据记录, 索引的 key 是数据表的主键
06
InnoDB 的主键选择与插入优化
在使用 InnoDB 存储引擎时, 建议使用一个与业务无关的自增字段作为主键
InnoDB 将数据记录本身存于主索引 (一颗 B+Tree) 的叶子节点上每当有一条新的记录插入时, MySQL 会根据其主键将其插入适当的节点和位置, 如果表使用自增主键, 那么每次插入新的记录, 记录就会顺序添加到当前索引节点的后续位置, 当一页写满, 就会自动开辟一个新的页如下图所示:
这样就会形成一个紧凑的索引结构, 近似顺序填满
如果使用非自增主键(如果身份证号或学号等), 由于每次插入主键的值近似于随机, 因此每次新纪录都要被插到现有索引页得中间某个位置:
此时 MySQL 不得不为了将新记录插到合适位置而移动数据, 甚至目标页面可能已经被回写到磁盘上而从缓存中清掉, 此时又要从磁盘上读回来, 这增加了很多开销, 同时频繁的移动分页操作造成了大量的碎片, 得到了不够紧凑的索引结构, 后续不得不通过 OPTIMIZE TABLE 来重建表并优化填充页面
因此, 只要可以, 请尽量在 InnoDB 上采用自增字段做主键
知道了这些基本知识, 如何加以运用呢? see you!
本文部分参考了关于介绍索引的文章:
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
以上, 如果疏漏错误, 请指正
希望时间的流逝不仅仅丰富了我们的阅历, 更重要的是通过提炼让我们得以升华, 走向卓越
来源: https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247485203&idx=1&sn=5e19d0814f1bd408d498a8890d460775&chksm=eb7c2ad8dc0ba3ce518eef004c8e5a9335d78ddece07ef3ac80dea09952a349c38916cf6fb22#rd