MySQL——索引原理

科技2022-08-15 94

MySQL的索引主要是用了B+树

B-树

B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图. B-树有如下特点:

所有键值分布在整颗树中；任何一个关键字出现且只出现在一个结点中；搜索有可能在非叶子结点结束；在关键字全集内做一次查找,性能逼近二分查找；

B+ 树

所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)为所有叶子结点增加了一个链指针

为什么使用 B+树

局部性原理与磁盘预读

局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用程序运行期间所需要的数据通常比较集中。

由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取，而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。

由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此对于具有局部性的程序来说，预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

B-/+Tree索引的性能分析

来自张洋的博客: 实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个结点只需一次I/O。假设 B-Tree 的高度为 h,B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

B+树更适合外部存储,由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B+树单次磁盘IO的信息量大于B-树,I/O效率更高。Mysql是一种关系型数据库，区间访问是常见的一种情况，B+树叶节点增加的链指针,加强了区间访问性，可使用在范围区间查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

InnoDB和MyISAM索引比较

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。叶节点包含了完整的数据记录。这种索引叫做聚集索引。

因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

MYISAM是按列值与行号来组织索引的。它的叶子节点中保存的实际上是指向存放数据的物理块的指针。从MYISAM存储的物理文件我们能看出，MYISAM引擎的索引文件（.MYI）和数据文件(.MYD)是相互独立的。

参考：MySQL索引背后的数据结构及算法原理：https://www.kancloud.cn/kancloud/theory-of-mysql-index/41850

聚簇索引和非聚簇索引

聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。一般情况下主键会默认创建聚簇索引，且一张表只允许存在一个聚簇索引。（InnoDB的数据文件本身就是索引文件）

在《数据库原理》一书中是这么解释聚簇索引和非聚簇索引的区别的：聚簇索引的叶子节点就是数据节点，而非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。

慢sql优化

慢查询产生的原因

慢查询的出现不能想当然归于表的记录数太多，表的记录数和慢查询之间并没有必然的关系。慢查询出现的常见原因：

没有正确使用索引或索引失效，导致全表扫描了表设计不合理，出现了多表JoinSQL本身的写法有问题，出现了大量的中间结果SQL返回结果集过大

所以慢查询应该重点从表的设计和SQL的写法上去解决，库内分表不是一个好的方案。

sql优化

select index from table_name; 找出所有索引 explain 显示sql的执行计划 extra 如果使用 using filesort 那么没有使用索引，速度可能就会很慢强制使用某个索引： select * from order force index(user_index) where del_flag = 0 and user_id = 110339 and status = 12 and language_code = 'zh' order by update_time desc limit 0,50; 忽略使用某个索引：select * from table ignore index（idx_update_time）

具体可以参考我的另一篇blog 《Mysql—— explain 执行计划》

TPS/QPS高

TPS高是拆库的最重要的依据，重构前订单表，优惠券表等大表都有数亿条数据，拆分的首要原因就是TPS撑不住了，超过6K从库就会开始有明显延迟。如果TPS不高但QPS很高，而且对数据的一致性要求不高，可以考虑读写分离方案。

水平分库：数据量过大时，为了缓解数据库压力，把相同的业务数据写入不同的数据库，不同的数据库中表结构必须相同。这种是共用一套service,service-api和controller垂直分库：不同的业务数据写入不同的数据库，不同的数据库中表结构可能是不同的。这种需要配置多个数据源，会有多套service,service-api和controller在垂直分库中又水平分库：不同的业务数据写入不同的数据库,在不同业务的数据库中又水平分库