消息队列是在消息的传输过程中保存消息的容器，简单点理解就是传递消息的队列，具备先进先出的特点，一般用于异步、解耦、流量削锋等问题，实现高性能、高可用、高扩展的架构。一个消息队列可以被一个或多个消费者消费，一般包含以下成员：

• Producer: 消息生产者，负责产生消息推送到Broker
• Broker：消息处理中心，负责消息存储、确认、重试，一般其中会有多个Queue
• Consumer：消息消费者，负责从Broker中获取消息，并进行相应处理

为什么要使用消息队列？

MQ的应用场景很多，有应用解耦、异步处理、流量削峰、日志处理、消息通信、消息广播等

但核心场景就三个：

• 解耦：将消息写入消息队列，需要消息的时候自己从消息队列中订阅，从而原系统不需要做任何修改。
• 异步：将消息写入消息队列，非必要的业务逻辑以异步方式运行，加快响应速度。
• 削峰：原系统按照数据库能处理的并发量从消息队列中拉取消息，在生产中，短暂的高峰期积压是被允许的。

解耦

假设有以下场景，用户向订单系统进行请求下单，订单系统中的逻辑调用为在下单成功之后还要调用积分系统、交易系统、短信系统，而其中短信系统调用失败了。但因为整个流程没有解耦，导致整个流程回滚且反馈给用户下单失败。

而引入MQ后，整个流程就解耦很多了，用户调用订单系统下单，订单系统在处理完订单相关事宜后发送消息到消息队列，下游系统再根据topic、tag等内容进行消息的消费，积分系统、交易系统、短信系统的成功与否不影响订单系统的流程，订单系统可以直接反馈下单成功的信息。

而如果再进一步，订单相关是公司的其中一个业务部门，此时有场景是用户下单后需要推送到大数据等部门做一些统计分析类的工作，如果此时有以下场景

1. A部门需要在订单数据的基础上增加用户相关信息数据X
2. B部门需要在订单数据的基础上增加用户历史购物数据Y
3. C部门只需要订单数据的部分数据
4. D部门需要订单数据，但需要进行封装

如果不考虑MQ，那么这些操作都是需要修改代码才能实现，几个系统都耦合在一起了。

而引入MQ后，不需要在订单系统主动调用其他接口推送数据，只需要把数据推送到MQ中，哪些部门需要数据就自己去拉取就可以了。

异步

假设现在积分、交易、短信系统都是第三方服务，第三方服务可能会有宕机、执行缓慢的稳定性差的情况。如果没有MQ，当接口故障的时候要自己去编写重试逻辑（不关同步异步），还要考虑如果重试失败了是否要持久化下来在某个时间点通过定时任务重新推送，这一整个逻辑不仅仅影响功能复杂性，还影响性能。

如果有MQ，那么只需要把消息推送到MQ中，再从MQ中消费就可以了，如果接口不可用，直接给MQ返回消费失败，下次还可以重新拉取消息进行消费，不需要编写复杂的重试代码。

削峰

大部分业务中的性能瓶颈都会在数据库，假设数据库可以支撑5k qps，但是在某些场景中（比如双十一、618活动）中qps可能有3w甚至5w、10w，这时候巨大的压力会把数据库打爆。

而MQ扛几万的并发几乎没有任何问题，这时候我们就可以引入MQ，请求先写入到MQ中，再从MQ中慢慢消费落库。

此时写入MQ的QPS在3w，但消费MQ只有5k，积压的请求可以在后面慢慢消费，这样子可以扛住高于甚至远高于数据库可支撑的请求数量

消息队列有什么缺点？

引入新技术解决问题的同时会带来新的问题，只不过如果解决新问题比解决旧问题容易，那么引入新技术就是利大于弊的。

引入MQ也会带来问题，比如：

• 系统可用性降低：引入的外部依赖越多就越容易挂掉，比如上文提到，ABCD四个系统要采集订单系统的数据，老方法是订单系统完成后调用ABCD四个系统的接口，但是引入了MQ，如果MQ挂了，那ABCD也用不了了。
• 系统复杂度提高：本来架构技术栈很简单，但是引入了MQ，导致一些数据丢失、重复消费的问题，会使系统复杂度大大提高。
• 一致性问题：还是ABCD四个系统采集订单系统数据，订单系统完成后调用ABCD接口，调用B失败就不再调用BCD而直接回滚数据了，结果引入了MQ，订单系统在完成下单后推送消息到MQ就直接返回成功了，但实际上可能只有ABC成功了，D失败了，这时候要通过其他手段来保证数据一致性。

消息队列模型

• 点对点模式：多个生产者可以相同一个消息队列发送消息，一个消息只能被一个消费者消费，消费成功后这个消息会被移除，如果消费者处理消息失败了，那这条消息会重新被消费。

• 发布-订阅模式：单个消息可以被多个消费者并发获取、处理。多个生产者可以将多个消息写到同一个topic中，被同一个消费者消费（topic中可以通过tag区分）

消息队列的选择

市面上常用的消息队列有Kafka、RocketMQ、RabbitMQ、ActiveMQ

下面根据特性和数据进行对比

综上：

• Kafka 和 RocketMQ 都支持 10w 级别的高吞吐量。
• Kafka 一开始的目的就是用于日志收集和传输，适合有大量数据产生的互联网业务，特别是大数据领域的实时计算、日志采集等场景，用 Kafka 绝对没错，社区活跃度高，业内标准。
• RocketMQ特别适用于金融互联网领域这类对于可靠性要求很高的场景，比如订单交易等，而且 RocketMQ 是阿里出品的，经历过那么多次淘宝双十一的考验，大品牌，在稳定性值得信赖。但如果阿里不再维护这个技术了，社区有可能突然黄掉的风险。因此如果公司对自己的技术实力有自信，基础架构研发实力较强，推荐用 RocketMQ。
• RabbitMQ 适用于公司对外提供能力，可能会有很多主题接入的中台业务场景，毕竟它是百万级主题数的。它的时效性是毫秒级的，但实际毫秒级和微秒级在感知上没有什么太大的区别，所以它的这一大优点并不太会作为考量标准。同时，它的功能是比较完善的，开源社区活跃度高，能解决开发中遇到的bug，所以万级别数据量业务场景的小公司可以优先选择功能完善的RabbitMQ。它的缺点就是用 Erlang 语言编写，所以很多开发人员很难去看懂源码并进行二次开发和维护，也就是说对于公司来说可能处于不可控的状态。
• ActiveMQ现在很少有人用，没怎么经过大规模吞吐量场景的考验，社区不怎么活跃，官方社区现在对 ActiveMQ 5.x 维护也越来越少，所以不推荐使用。

背景

一个服务有多个二进制，每个二进制有对应的编译信息，判断编译信息不存在时，则插入数据。

执行的时候却发现，对一个服务的多个二进制的编译信息进行插入时，发生了死锁。

简化问题

抛开业务属性，对于表building

CREATE TABLE `building` (
 `appid` int(11) DEFAULT 0,
 `buildid` int(11) DEFAULT 0,
 KEY `idx1` (`appid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci

执行以下语句时，发生了死锁：

begin
    select * from building where appid = 5 for update;
    // 判断结果为空，则插入数据
    insert into building values (5, 1);
commit

即，并发执行select for update + insert时导致死锁

先解决问题

死锁的原因

首先，使用的MySQL版本为5.7.18，使用了默认的隔离级别可重复读（Repeatable read）。 假设执行语句前数据库里有如下数据：

执行过程如下

说明原因：

• 步骤3和4同时持有了gap锁，非互斥，都到了下一步
• 步骤5的插入意向锁与步骤4的gap锁冲突，卡住
• 步骤6的插入意向锁和步骤3的gap锁冲突，卡住，但是数据库发现有环，直接报错死锁
• ps: 步骤6报错并回滚之后，transaction 1是可以执行的。

解决方案：

1. 可以修改隔离级别为已提交读（Read Committed），就不会有gap lock的问题【备注：未解决业务问题】
2. 可以修改索引类型为唯一索引，然后就不需要先select再insert了，直接insert（可能报错） 或者insert ignore，insert ... on duplicate key update【备注：实际情况复杂一些，不只是appid单列的唯一索引】

引发的思考：

1. 隔离级别有影响么？
2. 表中包含哪些原始数据，有关系么？
3. 语句3和4在where条件一样的时候就会互斥么？
4. 间隙锁（gap lock）和插入意向锁(intert intention lock)作用到底是什么？
5. 最初写这个事务的目的是为了防止同appid的并发插入问题（即上述例子中， 步骤4的 where语句条件为appid=5），能正确执行么？

MySQL的知识点

隔离级别

一般来讲，上表中从上到下按照隔离的级别由低到高，越高的隔离，效率越差。

• 脏读 :一个事务读取到另一事务未提交的更新数据
• 不可重复读 : 在同一事务中,多次读取同一数据返回的结果有所不同, 换句话说, 后续读取可以读到另一事务已提交的更新数据。相反, “可重复读”在同一事务中多次读取数据时, 能够保证所读数据一样, 也就是后续读取不能读到另一事务已提交的更新数据。
• 幻读 : 并不是说两次读取获取的结果集不同，幻读侧重的方面是某一次的select操作得到的结果所表征的数据状态无法支撑后续的业务操作。更为具体一些select某记录是否存在，不存在，准备插入此记录，但执行insert时发现此记录已存在，无法插入，此时就发生了幻读。

不可重复读例子：

设置隔离级别为Read Committed。

幻读例子

设置隔离级别为Repeatable Read，将appid改为唯一索引。

锁分类

1. 锁类型

• 表锁：

  • 对一整张表加锁，一般是DDL(数据定义语言)处理时使用，也可以自己在SQL中指定。由MySQL服务器实现。
  • 特点：开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概率最高，并发度最低；

• 行锁:

  • 锁定某一行数据或某几行，或行和行之间的间隙。由存储引擎实现，常见的就是InnoDB。行锁是加在索引上的（MyISAM存储引擎只能使用表锁）。
  • 特点：开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度也最高。

• 行锁细分（上面的问题主要就集中在这里介绍的锁上）

  • 记录锁（Record Lock）

    • 锁直接加在索引记录上面，锁住的是key。没有显示索引时，会用数据库隐式创建的一个索 引。如果Where条件中指定的列是非聚簇索引，那么记录锁不仅会加在该索引上，还会加在对应的聚簇索引上。

  • 间隙锁（Gap Lock）

    • 锁定索引记录间隙，确保索引记录的间隙不变。间隙锁在事务隔离级别为可重复读或以上级别时生效。 MySQL使用间隙锁可以防止其他事务在该范围内插入或修改记录，保证两次读取这个范围内 的记录不会变，从而防止出现幻读现象。 对于上面的例子，执行事务前间隙包括：（-∞,10），（10,20），（20,30），（30,+∞）。执行期间where语句的条件落在了同一个间隙中，因此互相锁住。同时，值得注意的是间隙锁之间并不互斥。

  • Next-Key Lock

    • 即行锁和间隙锁组合起来，是加在某条记录以及这条记录前面间隙上的锁。（疑问：实际操作 发现，where命中记录时，条件前后的间隙都会加锁，而不是只有前面间隙） Next-Key锁同间隙锁一样在事务隔离级别为可重复读或以上级别时生效。Locking reads（select ... for update或lock in share mode），Update和Delete时，除了对唯一 索引的唯一搜索外都会获取gap锁或next-key锁。即锁住其扫描的范围。"唯一索引的唯一搜 索"表示where条件用了唯一索引且搜索到了记录。

  • 插入意向锁（Insert Intention Locks）

    • 一种特殊的间隙锁，用于Insert的时候。插入意向锁只会和间隙锁或Next-Key锁冲突，和插入意向锁并不冲突。

锁兼容矩阵

事务A想对数据R获取(row)的锁，但是数据已持有(col)的锁时的兼容性。

第一列表示已经有的锁，第二列到第五列表示待加的锁。

注意此矩阵并不对称。

主要是一个事务已经获取了插入意向锁，对其他事务是没有任何影响的。而一个事务想要获取插入意向锁，如果有其他事务已经加了间隙锁或Next-Key锁，则会阻塞.

2. 锁模式

• 读锁（S）

  • 又称共享锁，加了读锁的记录，所有的事务都可以读取，但是不能修改，并且可同时有多个事 务对记录加读锁。

• 写锁（X）

  • 又称排他锁，加了写锁的记录，只有拥有该锁的事务可以读取和修改，其他事务都不可以读取 和修改，并且同一时间只能有一个事务加写锁。

• 读意向锁（IS）

  • 为表级锁，当事务试图读某一条记录时，会先在表上加上读意向锁，这样判断表中是否有记录 加锁就很简单了。

• 写意向锁（IX）

  • 为表级锁，当事务试图写某一条记录时，会先在表上加上写意向锁，这样判断表中是否有记录 加锁就很简单了（例如，判断其他事务已表上加IX锁，则本事务无法在表上加X锁）。

锁兼容矩阵：

3.相关命令

查看全局和会话事务隔离级别

select @@global.tx_isolation;
select @@session.tx_isolation;
select @@tx_isolation;

设置当前session的隔离级别

set session transaction isolation level repeatable read

展示事务的相关信息（包括锁）

show engine innodb status // 结果中的TRANSACTIONS部分

展示锁相关信息

select * from information_schema.innodb_locks;

细分问题的解答

1. 隔离级别有影响么？

• 答：有，RR隔离级别及以上才有Gap lock, Next-Key lock。

2. 表中包含哪些原始数据，有关系么？

• 有，影响Gap lock的范围

3. 语句3和4在where条件一样的时候就会互斥么？

• 不是，需要where中使用唯一索引且命中记录

3. gap lock和intert intention lock作用到底是什么？
4. 最初写这个事务的目的是为了防止同appid的并发插入问题（即上述例子中， 步骤4的where语句条件为appid=5，能正确执行么？

• 这个问题需要再稍微展开说明一下。其实最初select + insert的本意是为了先查找某条数据（的 索引），确认其不存在，然后插入数据。没意识到查找会影响其他数据（即上面的appid = 5和appid = 6互相影响了）。
• 而用select ... where ... for update的初衷应该是希望对同一个索引有相互阻塞作用，讲人话就是想要在一条不存在的记录上加上互斥的读锁（如果已存在的话，insert不会发生，不会产生额外的数据，也就无所谓了）。

• 那么，这个情况是MySQL能解决的么？

  • 很遗憾，答案是不能。

  • 可这种情况确实存在怎么办呢？可能有如下的解法：

    1. 用mutex table。

       • 即在另一张有唯一索引，且确保索引对应的记录存在的行上进行select ... for update操作。对上面的例子来说，select * from app where id = 5 for update即可（因为用appid=5查building的时候，id为5的app记录已经存在了）

    2. 改用唯一索引，并舍弃掉select...for update操作。

       • 可以改用insert ignore即可，让MySQL自身保证不会有重复数据。

    3. 重试。

       • 不管是前面例子的问题，还是本问题，其实MySQL发现死锁后，会立即回滚，结果就是有一个事务会成功。失败的事务，重试即可。【备注：并发多的时候，可能会需要重试多次】
    4. 用GET_LOCK / RELEASE_LOCK。
    5. 用redis等其他系统来加锁。

  上面的例子中方法1，2，3应该都可以。值得注意的是，部分情况下2不可行，例如判断如果不存在，则一次插入多条数据的情况。

如果您能看到我的blog并且感到有帮助, 我倍感荣幸

我们知道, Redis是一个键值型（Key-Value Pair）的数据库, 我们可以根据键实现快速的增删改查。而Dict数据结构在其中更是起到了非常非常重要的作用, 我们甚至可以认为, 整个redis其实就是一个巨大的Dict。
而键与值的映射关系正是通过Dict来实现的。

这次文章内容比较多, 所以我很多内容都在注释里 一定要看注释呀！

[...]

最近学习了黄建宏大佬的《redis设计与实现》，真心觉得redis非常非常强（建宏大佬也强），但是我觉得书本的阅读始终是入门, 真正要深入redis的思想和原理，还是要去看一看源码。

于是我就在redis源码下载地址上下载了redis7.0.4版本的源码；结合网上一些大佬的博客，开始阅读redis。

redis源码阅读起来并不是一件简单的事情，并且也想着不是阅读一次就算了，我决定开个blog记录一下阅读的内容。

如果您能看到我的blog并且感到有帮助，我倍感荣幸

[...]

最近学习了黄建宏大佬的《redis设计与实现》，真心觉得redis非常非常强（建宏大佬也强），但是我觉得书本的阅读始终是入门, 真正要深入redis的思想和原理，还是要去看一看源码。

于是我就在redis源码下载地址上下载了redis7.0.4版本的源码；结合网上一些大佬的博客，开始阅读redis。

redis源码阅读起来并不是一件简单的事情，并且也想着不是阅读一次就算了，我决定开个blog记录一下阅读的内容。

如果您能看到我的blog并且感到有帮助，我倍感荣幸

[...]

为什么MySQL要用B+树？

​ 这是数据库相关面试中非常常见的问题，对于这个问题我听过很多答案，例如：B+树节点存id节约空间、B+树子树之间有指针、B+树只需要较低的层高就能存大量数据...

​ 并不是说这些答案不对，但是终究是有点片面。

​ 所以今天我们来系统的讨论下，为什么MySQL要用B+树。

前言

首先要明白的一点是，B+树跟MySQL没有任何直接关系，真正跟B+树有关系的是MySQL的存储引擎，而存储引擎的主要作用是负责数据的存储和提取。

MySQL的默认存储引擎是InnoDB，当然也可以使用MyISAM，今天不讨论MyISAM，只说说InnoDB。那么问题来了？为什么MySQL的默认存储引擎InnoDB要使用B+树来作为数据的存储结构呢？

​ 相信有阅读过MySQL索引章节的同学们都了解过，表中的索引不论是主键还是辅助索引都会使用B+树进行存储，前者使用的存储方式是<id, row>，后者的方式是<row_index, id>。这也比较容易理解：

• 在主键（聚簇索引）中，id是主键，数据库通过id去查找数据行。
• 在非聚簇索引（辅助索引）中，索引的列（或者说数据行的列）构成了主键，通过索引的列去找到索引的id。（如果有需要，还可以通过id去找当前数据行的全部内容，这也是为什么辅助索引需要再回表的原因）

讨论

现在疑问来了，InnoDB为什么要用B+树呢？用B树不行吗？用hash表不行吗？ok，我们从两个角度来分析这个问题：

• InnoDB 需要支持的场景和功能需要在特定查询上拥有较强的性能
• CPU 将磁盘上的数据加载到内存中需要花费大量的时间

这其实就是我们使用数据库最平常不过的两个操作：对数据的持久化与对持久化数据的查询。实时查询数据需要快，而持久化数据需要IO，在这两者同时兼顾的情况下，B+树成为了最好的选择。

读写性能

​ MySQL作为传统的关系型数据库（OLTP），InnoDB作为传统关系型数据库的存储引擎，通常要用来执行以下操作：

• 通过Insert、Delete、Update对单行数据进行增删改
• 通过 Update 和 Delete 语句对符合条件的数据进行批量的删除；
• 通过 Select 语句和主键查询某条记录的全部列；
• 通过 Select 语句在表中查询符合某些条件的记录并根据某些字段排序；
• 通过 Select 语句查询表中数据的行数select count(*)；
• 通过唯一索引保证表中某个字段或者某几个字段的唯一性；

如果我们尝试对一条数据进行修改/访问时，SQL执行的时间复杂度时O(logN),而N是树的高度。但是这时候有小伙伴就要问了：

• 啊！你这O(logN)，Hash表读可是可以达到O(1)的！B+树8彳亍！

虽然对于读取单条数据的场景说，哈希表确实爆杀B+树，但是不要忘了，我们还有范围查询的场景：

select * from table where age='22' order by desc; 

select * from table where age > 18;

update table set features = '超级帅' where name = '十七';

delete from table where name = 'hug';

​ 我们都知道哈希表的原理是根据字符串进行哈希然后均摊在哈希桶中，而哈希表不论是哈希桶还是哈希值都是无序的。

​ 这就意味着，当遇到范围匹配的场景时，哈希表构成的索引就完全没有用处了，只能进行全表查询并且一个一个的去判断是否满足条件。而全表查询对于数据库来说十分的糟糕！==（所有的查询都应该避免全表查询！）==换句话说，在范围查询时，哈希表有跟无， 没有区别。

​ 而B+树是能够保证数据按照主键的顺序进行存储，也就是说在B+树中，相邻的数据其实都是按照自然顺序排列的（这里就不讲B+树的原理了）

​ 这时候又有小伙伴要问了：

• 啊！不是还有B树吗！B树也可以排列啊！为啥不用B树！（是不是因为作者没有B树！）

​ B树和B+树在数据结构上确实是类似的，他们都可以按照顺序对索引中的内容进行遍历，对于排序和范围查询等操作，B树相对于B+树来说会有更好的性能。（当然如果索引建的比较差劲或者SQL写的复杂，也是会全表查询。）

小结

与 B 树和 B+ 树相比，哈希作为底层的数据结构的表能够以 O(1) 的速度处理单个数据行的增删改查，但是面对范围查询或者排序时就会导致全表扫描的结果。

而 B 树和 B+ 树虽然在单数据行的增删查改上需要 O(log n) 的时间，但是它会将索引列相近的数据按顺序存储，所以能够避免全表扫描。

数据加载

我们来回答小伙伴的问题，哈希表已经被我们排除了，B+树和B树一样都可以相对高效的执行查询，那为什么不选择B树？

这时候我们就要来讨论第二个因素——数据加载

先来说说读取数据

稍微了解操作系统的小伙伴们都知道，计算机在读取文件的时候会按页为单位将数据读到内存中。页的大小在大多数操作系统上都是4KB，可以通过

$ getconf PAGE_SIZE
16384/4096 ...

来获取，我的电脑一页是16KB，因操作系统不同而不同。

在我们执行查询数据时，CPU会发现当前数据在磁盘里而不是内存中，这时候就会触发I/O将数据从磁盘中读入内存中进行访问。而我们都知道数据从磁盘读到内存的成本非常大。就以普通磁盘为例，加载数据需要经过队列、寻道、旋转、传输等过程，总计算大约需要10ms的时间。

回到数据库

一般我们估算MySQL查询时间时就可以用10ms来衡量随机I/O时间，这里需要特别说一下，这个时间指的是随机I/O的时间，顺序读取磁盘数据是可以达到40MB/s的，两者差距是几个数量级，因此在日常开发中，要注意减少随机I/O的次数，以提高性能。

而B树和B+树最大的区别在于，B树可以在非叶子结点中存储数据，但是B+树的所有数据都存在叶子结点中，下面来举个栗子，假设有以下语句：

select * from table where id > 3 and id < 9

那么，如图所示：

如果我们不考虑优化，在上面的B树中执行查询的顺序是：

1. 加载根节点，发现根节点第一个元素是5，大于3（第一次随机I/O）
2. 通过根节点加载左叶子节点，遍历叶子结点的数据，找到匹配的数据（第二次随机I/O)
3. 加载回根节点，发现根节点不包含第二个元素（第三次随机I/O）
4. 加载右叶子节点，遍历叶子结点数据，找到匹配的数据（第四次随机IO）

由此得出，执行上面的简单的查询语句在B树中我们需要进行4次随机IO才能找到所有满足条件的行，当然我们也可以用各种方式来优化查询，不过，B树能做的优化基本上B+树都可以。但有的优化，B+树可以，B树不彳亍。

B+树可以，B树不行的优化

由于所有的节点都可能包含目标数据，我们总是要从根节点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机 I/O，也是 B 树最大的性能问题。

但B+ 树中就不存在这个问题了，B+树所有的数据行都存储在叶节点中，而这些叶节点可以通过指针依次按顺序连接，遍历数据时可以直接在多个子节点之间进行跳转，这样能够节省大量的磁盘 I/O 时间，也不需要在不同层级的节点之间对数据进行拼接和排序。

通过一个 B+ 树最左侧的叶子节点，我们可以像链表一样遍历整个树中的全部数据，也可以引入双向链表保证倒序遍历时的性能。

当然，有的小伙伴可能就会问了：

• 啊！你这个B+树的结构会因为数据量不断增加高度从而增加整体的耗时！

然而，根据B+树的原理高度为 3 的 B+ 树就能够存储千万级别的数据，实践中 B+ 树的高度最多也就 4 或者 5，所以不用担心，这不是性能瓶颈。

总结

如果一个设计不考虑场景，那么所有的设计都是纸上谈兵

当我们了解需求场景和使用原理，再对不同的数据结构进行选择就成了理所当然的事情。只能说，B+树不是最好的数据结构，但是对于MySQL来说，B+树就是合适的结构，他能在尽量优秀的情况下解决大多数情况下MySQL会遇到的问题。

我们来把文章的内容总结一下，为什么MySQL默认的存储引擎选择B+树而不是哈希表或者B树呢？

原因：

• 哈希表有极其优秀的单数据操作性能，但是对于范围查询和排序却无能为力，反而会引起全表扫描。
• B树能够在非叶节点中存储数据，但是这也导致在查询连续数据时可能会带来更多的随机 I/O，而 B+ 树的所有叶节点可以通过指针相互连接，能够减少顺序遍历时产生的额外随机 I/O。

当然，有的小伙伴可能会问了：

• 啊！我就不能两个都用吗！单行数据的时候我用哈希，顺序查询的时候我用B+树！

答案是当然可以，但是必须能够容忍更高的复杂度。

在同一张表上可以同时建哈希表和B+树构成的存储结构，这样在不同的操作时可以选择更快的数据结构，但是！这会导致更新和删除时在redo log中操作更多份数据，总表的体积也会变得非常非常大

从今天的角度来看，B+树可能不是 InnoDB 的最优选择，但是它一定是能够满足当时设计场景的需要。

结尾引用自draveness大大的一句话

数据库、程序、系统设计思想的发展到今天已经过了几十年的时间，我们不得不说优秀的工程设计确实有足够的生命力。而我们作为工程师，在设计系统、设计算法、设计数据结构时也应该非常清楚地知道不同数据结构、程序架构适合的场景，因为软件工程中没有银弹。

Reference

• Draveness Blog: whys the design ?
• B+ tree · Wikipedia
• What is the difference between Mysql InnoDB B+ tree index and hash index? Why does MongoDB use B-tree?
• B+Trees and why I love them, part I
• What are the main differences between INNODB and MYISAM
• B+ Tree File Organization
• Database Index: A Re-visit to B+ Tree
• Fundamentals of database systems