mysql索引为什么用b+树而不是b树_mysql索引？为什么用b+树？

理论详解：为什么 MySQL 采用B+树作为索引？ 　　MySQL选择B+树作为索引结构有着很多优势，包括平衡性、支持范围查询、顺序访问性能和插入删除操作的高效性。这些特性使得B+树成为了数据库索引的首选结构。 　　MySQL采用B+树作为索引的主要原因有以下几点： 　　1. 高效的范围查询：B+树的叶子节点是按照顺序链接的，这使得范围查询非常高效。在B+树上进行范围查询时，只需要遍历叶子节点上的连续数据即可，而不需要遍历整个索引树。 　　2. 适应磁盘IO：B+树的节点大小通常和磁盘页大小相等，这样可以最大程度地减少磁盘IO次数。B+树的层级较低，树的高度相对较小，这进一步减少了磁盘IO的次数。 　　3. 可以支持有序性查询：B+树的叶子节点是按照顺序链接的，这使得B+树非常适合支持有序性查询。对于需要按照索引顺序进行查询的场景，B+树可以非常高效地处理。 　　4. 支持高效的插入和删除操作：B+树的插入和删除操作相对较为简单高效。插入操作只需要找到合适的位置并进行插入，删除操作只需要删除对应的节点即可。相比于其他树结构，B+树的插入和删除操作所需的平均IO次数更少。 　　5. 支持多级索引：B+树的内部节点除了存储键值对外，还可以存储其他节点的指针，这使得B+树可以支持多级索引。多级索引可以减小索引的大小，提高索引的效率。 　　综上所述，MySQL采用B+树作为索引是为了提高查询效率、适应磁盘IO、支持有序性查询、支持高效的插入和删除操作以及支持多级索引等方面的考虑。 　　因为要保证性能，还要保证查询效率 　　让我们先来了解一下计算机的数据加载。 　　磁盘IO和预读： 　　

　　先说一下磁盘IO，磁盘读取数据靠的是机械运动，每一次读取数据需要寻道、寻点、拷贝到内存三步操作。 　　寻道时间是磁臂移动到指定磁道所需要的时间，一般在5ms以下； 　　寻点是从磁道中找到数据存在的那个点，平均时间是半圈时间，如果是一个7200转/min的磁盘，寻点时间平均是/7200/2=4.17ms； 　　拷贝到内存的时间很快，和前面两个时间比起来可以忽略不计，所以一次IO的时间平均是在9ms左右。听起来很快，但数据库百万级别的数据过一遍就达到了9000s，显然就是灾难级别的了。 　　

　　

　　考虑到磁盘IO是非常高昂的操作，计算机操作系统做了预读的优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。 　　每一次IO读取的数据我们称之为一页(page)，具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO。 　　（突然想到个我刚毕业被问过的问题，在64位的操作系统中，Java中的int类型占几个字节？最大是多少？为什么？） 　　那我们想要优化数据库查询，就要尽量减少磁盘的IO操作，所以就出现了索引。 　　索引是什么？ 　　MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效数据的数据结构。 　　MySQL中常用的索引在物理上分两类，B-树索引和哈希索引。 　　本次主要讲BTree索引。 　　BTree索引 　　BTree又叫多路平衡查找树，一颗m叉的BTree特性如下：树中每个节点最多包含m个孩子。除根节点与叶子节点外，每个节点至少有[ceil(m/2)]个孩子（ceil()为向上取整）。若根节点不是叶子节点，则至少有两个孩子。所有的叶子节点都在同一层。每个非叶子节点由n个key与n+1个指针组成，其中[ceil(m/2)-1] <= n <= m-1 。

　　这是一个3叉（只是举例，真实会有很多叉）的BTree结构图，每一个方框块我们称之为一个磁盘块或者叫做一个block块，这是操作系统一次IO往内存中读的内容，一个块对应四个扇区，紫色代表的是磁盘块中的数据key，黄色代表的是数据data，蓝色代表的是指针p，指向下一个磁盘块的位置。 　　来模拟下查找key为29的data的过程： 　　1、根据根结点指针读取文件目录的根磁盘块1。【磁盘IO操作1次】 　　2、磁盘块1存储17，35和三个指针数据。我们发现17<29<35，因此我们找到指针p2。 　　3、根据p2指针，我们定位并读取磁盘块3。【磁盘IO操作2次】 　　4、磁盘块3存储26，30和三个指针数据。我们发现26<29<30，因此我们找到指针p2。 　　5、根据p2指针，我们定位并读取磁盘块8。【磁盘IO操作3次】 　　6、磁盘块8中存储28，29。我们找到29，29所对应的数据data。由此可见，BTree索引使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。 　　但是有没有什么可优化的地方呢？ 　　我们从图上可以看到，每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。 　　B+Tree索引 　　B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。 　　

　　B+Tree相对于B-Tree有几点不同： 　　非叶子节点只存储键值信息， 数据记录都存放在叶子节点中， 将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，所以B+Tree的高度可以被压缩到特别的低。 　　具体的数据如下：InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。 也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。（这种计算方式存在误差，而且没有计算叶子节点，如果计算叶子节点其实是深度为4了） 　　我们只需要进行三次的IO操作就可以从10亿条数据中找到我们想要的数据，比起最开始的百万数据9000秒不知道好了多少个华莱士了。 　　而且在B+Tree上通常有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。所以我们除了可以对B+Tree进行主键的范围查找和分页查找，还可以从根节点开始，进行随机查找。 　　数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。 　　上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据，辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。 　　当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。 　　

　　不过，虽然索引可以加快查询速度，提高 MySQL 的处理性能，但是过多地使用索引也会造成以下弊端：创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。除了数据表占数据空间之外，每一个索引还要占一定的物理空间。如果要建立聚簇索引，那么需要的空间就会更大。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。注意：索引可以在一些情况下加速查询，但是在某些情况下，会降低效率。 　　索引只是提高效率的一个因素，因此在建立索引的时候应该遵循以下原则：在经常需要搜索的列上建立索引，可以加快搜索的速度。在作为主键的列上创建索引，强制该列的唯一性，并组织表中数据的排列结构。在经常使用表连接的列上创建索引，这些列主要是一些外键，可以加快表连接的速度。在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，所以其指定的范围是连续的。在经常需要排序的列上创建索引，因为索引已经排序，所以查询时可以利用索引的排序，加快排序查询。在经常使用 WHERE 子句的列上创建索引，加快条件的判断速度。 　　现在大家知道索引为啥能这么快了吧，其实就是一句话，通过索引的结构最大化的减少数据库的IO次数，毕竟，一次IO的时间真的是太久了。 　　作为一个热爱数据库技术的老程序员，我很高兴帮你深入了解MySQL中B+树索引的选择。 　　MySQL作为开源世界的宠儿，它的索引选择对性能至关重要。 　　让我们一步步分析这个选择。 　　基本使用：为什么是B+树 　　1、高效的查找和范围查询：B+树的结构使得数据能够按顺序存储和快速访问。这对于数据库的等值查询和范围查询尤为重要。 　　2、更好的磁盘I/O性能：B+树的设计减少了磁盘I/O操作。由于其所有叶子节点都是相互链接的，所以在进行范围查询时特别高效。 　　3、节省空间：在B+树中，只有叶子节点包含数据信息，中间节点仅存储键信息，这使得B+树的层级比B树更少，从而可以存储更多的键。 　　4、适合频繁的读操作：数据库操作通常是读取密集型的，B+树提供了对这种操作的优化。 　　最近无意间获得一份阿里大佬写的刷题笔记，一下子打通了我的任督二脉，进大厂原来没那么难。 　　这是大佬写的， 7701页的BAT大佬写的刷题笔记，让我offer拿到手软 　　性能优化 　　在MySQL中，通过合理使用B+树索引，可以显著提高查询效率。 　　选择合适的索引列：对于查询频繁的列创建索引，特别是那些WHERE子句中常用的列。 　　复合索引的顺序：在创建复合索引时，根据查询的频率和过滤效率来决定列的顺序。 　　索引维护：定期检查和优化索引，避免索引碎片化。 　　开源生态 　　MySQL的开源生态也是选择B+树的一个重要因素。由于MySQL是开源的，它的性能和特性经过了广大社区的充分测试和优化。B+树作为一个广泛应用于数据库系统的成熟数据结构，得到了广泛的支持和优化。 　　使用场景 　　举例说明B+树索引在MySQL中的应用： 　　电商平台商品查询：在商品表上针对商品类别、价格等字段建立索引，可以快速筛选出用户感兴趣的商品。 　　社交网络好友关系查询：在社交网络中，使用索引可以快速找到用户的好友列表。 　　日志数据检索：对于存储大量日志数据的表，通过在时间戳上建立索引，可以快速查询特定时间段的日志记录。 　　推荐一个学习 MySQL 的专栏文章 　　01、MySQL MariaDB 基础教程02、MySQL 简介03、MySQL MariaDB 安装04、MySQL 管理05、MySQL 日常管理06、MySQL PHP 语法07、MySQL 创建连接08、MySQL 数据库列表09、MySQL 创建数据库10、MySQL 删除数据库11、MySQL 选择数据库12、MySQL 数据类型13、MySQL 列出数据表14、MySQL 创建数据表15、MySQL 删除表16、MySQL 插入数据17、MySQL 插入数据的 ID18、MySQL SELECT FROM 查询数据19、MySQL WHERE 子句有条件的查询数据20、MySQL UPDATE 更新数据21、MySQL DELETE FROM 语句删除数据22、MySQL 返回删改查受影响的行数23、MySQL LIKE 子句模糊查询数据24、MySQL UNION 操作符查询多张表25、MySQL ORDER BY 排序26、MySQL GROUP BY 分组查询数据27、MySQL JOIN 进行多表查询28、MySQL NULL 值处理29、MySQL REGEXP 子句正则表达式查询30、MySQL 数据库事务31、MySQL ALTER 命令32、MySQL 索引33、CREATE TEMPORARY TABLE 创建临时表34、MySQL DROP TABLE 删除临时表35、MySQL INSERT INTO SELECT 复制表36、MySQL 服务器数据37、MySQL 自增序列 AUTO_INCREMENT38、MySQL 处理重复数据39、MySQL 安全及防止 SQL 注入攻击40、MySQL 导出数据41、MySQL 导入数据 　　真实案例 　　大型金融系统的交易查询：在一个处理数百万交易的金融系统中，通过在交易日期、交易ID上建立B+树索引，极大地提高了查询效率。 　　在线零售商的库存管理：一个在线零售商的数据库中，使用B+树索引来快速更新和查询商品库存。 　　总的来说，MySQL选择B+树作为索引的主要原因是其高效的读取性能和对磁盘I/O的优化，这对于数据库系统来说至关重要。随着数据量的增长， 　　这种优化变得更加显著。在你的数据库实践中，合理地使用B+树索引可以带来巨大的性能提升。 　　不过，记得，任何技术选择都需要根据具体的应用场景来决定哦！ 　　最后说一句(求，求赞，别白嫖我) 　　最近无意间获得一份阿里大佬写的刷题笔记，一下子打通了我的任督二脉，进大厂原来没那么难。 　　这是大佬写的， 7701页的BAT大佬写的刷题笔记，让我offer拿到手软 　　项目文档&视频： 　　弟弟快看-教程，程序员编程资料站 | DDKK.COM 　　本文，已收录于，我的技术网站 ddkk.com，有大厂完整面经，工作技术，架构师成长之路，等经验分享 　　求一键三连：点赞、分享、收藏 　　点赞对我真的非常重要！在线求赞，加个我会非常感激！@架构师专栏