深入理解Mysql索引底层数据结构与算法

目录学前目标什么是索引概念索引诞生原因索引选择二叉树红黑树B树B树B树高为3为例为何查询这么快MYISAM存储引擎实现MYISAM磁盘文件结构MYISAM走索引查找步骤INNODB存储引擎实现INNODB为何建议建自增整型主键不建立主键情况二级索引INNODB为何建议整型主键NNODB为何建议自增Hash索引联合索引学前目标理解 MySQL 索引的本质掌握主流索引底层数据结构掌握 BTree 成为 MySQL 主流索引结构的原因理解千万级数据表基于 BTree 快速查找的原理区分聚集索引、非聚集索引等概念掌握 MyISAM 和 InnoDB 两大存储引擎的索引实现差异理解 InnoDB 推荐使用自增整型主键的底层原因掌握非主键索引的存储逻辑掌握联合索引的底层存储结构理解并能应用 MySQL 索引最左前缀优化原则。什么是索引概念MySQL设计的一种排好序高效率查询数据的数据结构。索引诞生原因数据存盘方式是数据在磁盘磁道中随机分布存储的不一定是连续的MYSQL与磁盘交互的方式称为IO读取IO读取次数越少说明查询效率越高为此为了减少这种IO交互次数MYSQL诞生了索引。索引选择选择合适的索引数据结构的本质减小树的高度树的高度越小查找次数少IO交互就少二叉树二叉树极端的情况就是链表高度太高红黑树一张表如果几千万数据虽然会平衡数据但是由于数据量太大树高也很大。B树在红黑树的基础上将节点空间划分的更大来存更多的索引就变成了B树所有的节点中的索引元素不重复无冗余索引每个节点存储节点和数据叶节点深度相同节点之间无指针链接B树叶子节点存索引与数据非叶子索引非叶子节点索引在叶子节点会重复有冗余索引叶子节点有双向指针链接B树与B树对比为何选B树特征B树B-TreeB树BTree节点存储内容索引数据非叶子节点仅索引叶子节点索引数据索引冗余无冗余索引只出现一次有冗余非叶子节点索引在叶子节点重复叶子节点连接无指针连接双向指针连接支持区间查询磁盘IO效率较低节点存数据单次IO读的索引少更高非叶子节点仅存索引单次IO读更多索引区间查询能力弱需遍历整棵树强叶子节点指针直接遍历B树高为3为例为何查询这么快B树的容量主要取决叶子与非叶子节点的容量非叶子节点容量取决于索引大小和指向下个节点的指针地址叶子节点容量主要取决于存取数据的多少。inndb中对于根节点存取最大的容量称为页大小为16348可以查询出来SHOWVARIABLESLIKEinnodb_page_size;索引使用主键索引类型为BIGINT占8字节指向其它节点的指针大小为6字节根节点中一个索引它的指针地址指向大小就占用14个字节页大小为16384字节所以根节点可存16384 / (8 6) ≈ 16384 / 14 ≈ 1170个索引指针。那么中间层也会有1170个指针叶子节点一行记录大小最大为1kb整个叶子节点大小也是16KB一个B树撑满就是1170*1170*16意味着存取的记录大约是2100多万条。所以2000多万条数据放在一个B树中它的树高仅仅是3意味着只要进行3次磁盘IO就能找到我们想要的数据并且InnoDB 针对索引查询性能做的核心优化时将B 树索引的根节点会被持久化常驻在内存中更加提高了查询效率。问题B树为何在优化B树的基础上将B树的非叶子节点数据放在了自己的叶子节点上B树每页大小也按照16KB来算因为B树所有节点是索引数据的每层是放16KB的数据对于2000多万条记录的树高来说将是16的阶乘。MYISAM存储引擎实现MYISAM磁盘文件结构MyISAM 的每个表在磁盘上会对应三个文件假设表名为mytable​mytable.frm​文件存储表结构定义 ​mytable.MYD存储表的实际数据mytable.MYI​ 文件存储表的所有索引。这种索引文件 (.MYI) 和数据文件 (.MYD) ​彻底分开的称为非聚集索引索引叶子节点存储的是指向数据文件中相应行物理位置指针。MYISAM走索引查找步骤SELECT*FROMusersWHEREid15;从根节点MYI索引文件开始逐层找出15这个索引值直到叶子节点也找出这个15索引值后叶子存储的结构是 ​(键值, 物理地址指针)对。再通过这个物理地址指针直接指向数据文件 MYD 中某一行记录的起始位置读取这个行数据。这个过程称为回表查询在 MyISAM 中​任何索引查询都需要进行回表查询。INNODB存储引擎实现InnoDB 的表主要涉及mytable.frm和mytable.ibd文件。它在构建索引树的时候将索引文件与数据文件放在了IBD同一文件下。意味表数据和索引都存储在自己的.ibd文件中这种索引也叫聚簇索引。对于构建主键索引时它的叶子节点存储主键行数据INNODB为何建议建自增整型主键不建立主键情况如果没有定义主键InnoDB 会先选择一个唯一的非空索引​​ 来代替主键作为聚簇索引。如果表中连一个唯一的非空索引都没有InnoDB 会在内部自动生成一个 ​6 字节的隐藏的、名为ROW_ID的列并用它来构建聚簇索引。二级索引在INNODB中除了主键索引外其它索引都可以称为​二级索引。二级索引的叶子节点存储的内容是(索引键值, 主键值)上面这个过程是会消耗MYSQL系统资源的。INNODB为何建议整型主键存储空间比字符串节点空间存储的索引就多树的层级也会很小减少IO交互。NNODB为何建议自增不是自增值会落到两数据之间如果页空间满了会分裂自增直接从后面页插入即可。Hash索引INNODB中还有一种Hash索引通过Hash算法来定位数据对于等值查询速度是极快的但是数据分布不均匀不支持范围查询。联合索引