面试官： B 树和 B+ 树有什么区别？

问各位小可爱一个问题：MySQL 中 B 树和 B+ 树的区别？

请自己先思考5秒钟，看看是否已经了然如胸？
 

好啦，时间到！

B 树和 B+ 树是两种数据结构，构建了磁盘中的高速索引结构，因此不仅 MySQL 在用，MongoDB、Oracle 等也在用，基本属于数据库的标配常规操作。

数据库要经常和磁盘与内存打交道，为了提升性能，通常需要自己去构建类似文件系统的结构。今天主要来看看数据库是如何利用磁盘空间设计索引的？

行存储和列存储

在学习构建磁盘数据的索引结构前，我们先通过行存储、列存储的学习来了解一些基本的存储概念，帮助你建立一个基本的认知。

目前数据库存储一张表格主要是行存储（Row Storage）和列存储（Column Storage）两种存储方式。行存储将表格看作一个个记录，每个记录是一行。以包含订单号、金额、下单时间 3 项的表为例，行存储如下图所示：

如上图所示，在计算机中没有真正的行的概念。行存储本质就是数据一个接着一个排列，一行数据后面马上跟着另一行数据。如果订单表很大，一个磁盘块（Block）存不下，那么实际上就是每个块存储一定的行数。类似下图这样的结构：

行存储更新一行的操作，往往可以在一个块（Block）中进行。而查询数据，聚合数据（比如求 4 月份的订单数），往往需要跨块（Block）。因此，行存储优点很明显，更新快、单条记录的数据集中，适合事务。但缺点也很明显，查询慢。

还有一种表格的存储方式是列存储（Column Storage），列存储中数据是一列一列存的。还以订单表为例，如下图所示：

你可以看到订单号在一起、姓名在一起、时间在一起、金额也在一起——每个列的数据都聚集在一起。乍一看这样的结构很低效，比如说你想取出第一条订单，需要取第 1 列的第 1 个数据1001，然后取第 2 列的第 1 个数据小明，以此类推，需要 4 次磁盘读取。特别是更新某一条记录的时候，需要更新多处，速度很慢。那么列存储优势在哪里呢？

优势其实是在查询和聚合运算。

在列存储中同一列数据总是存放在一起，比如要查找某个时间段，很有可能在一个块中就可以找到，因为时间是集中存储的。假设磁盘块的大小是 4KB，一条记录是 100 字节， 那么 4KB 可以存 40 条记录；但是存储时间戳只需要一个 32 位整数，4KB 可以存储 1000 个时间。更关键的是，我们可以把一片连续的硬盘空间通过 DMA 技术直接映射到内存，这样就大大减少了搜索需要的时间。所以有时候在行存储需要几分钟的搜索操作，在列存储中只需几秒钟就可以完成。

总结一下，行存储、列存储，最终都需要把数据存到磁盘块。行存储记录一个接着一个，列存储一列接着一列。前面我们提到行存储适合更新及事务处理，更新好理解，因为一个订单可以在相同的 Block 中更新，那么为什么适合事务呢？

其实适合不适合是相对的，说行存