B 树和 B+ 树有什么区别？ _B

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 中更新，那么为什么适合事务呢？
其实适合不适合是相对的，说行存储适合是因为列存储非常不适合事务。试想一下，你更新一个表的若干个数据，如果要在不同块中更新，就可能产生多次更新操作。更新次数越多，保证一致性越麻烦。在单机环境我们可以上锁，可以用阻塞队列，可以用屏障……但是分布式场景中保证一致性（特别是强一致性）开销很大。因此我们说行存储适合事务，而列存储不适合。
索引
接下来，我们在行存储、列存储的基础上，讨论如何创建一些更高效的查询结构，这种结构通常称为索引。我们经常会遇到根据一个订单编号查订单的情况，比如说select * from order where id=1000000，这个时候就需要用到索引。而下面我将试图通过二分查找的场景，和你一起讨论索引是什么。
在亿级的订单 ID 中查找某个编号，很容易想到二分查找。要理解二分查找，最需要关心的是算法的进步机制。这个算法每进行一次查找，都会让问题的规模减半。当然，也有场景限制，二分查找只能应用在排序好的数据上。
比如我们要在下面排序好的数组中查找 3：
1,3,5,8,11,12,15,19,21,25
数组中一共有 10 个元素，因此我们第一次查找从数组正中间的元素找起。如果数组正中间有两个元素，就取左边的那个——对于这个例子是 11 。我们比较 11 和 3 的值，因为 11 大于 3，因此可以排除包括 11 在内的所有 11 右边的元素。相当于我们通过一次运算将数据的规模减半。假设我们有 240 （1T 数据）个元素需要查询（规模已经相当大了，万亿级别），用二分查找只需要 40 次运算。