B树和B+树有何区别？

本文共计2095个文字，预计阅读时间需要9分钟。

背景+首先，来谈谈B树。为什么要使用B树？我们需要明确以下两个事实：

1.不同容量的存储器，访问速度差异悬殊。

2.以磁盘和内存为例，访问磁盘的时间大约是ms级，而访问内存的时间则是ns级的。

因此，我们需要一种数据结构来平衡不同存储器的访问速度差异。B树就是这样一种数据结构。

背景

首先，来谈谈B树。为什么要使用B树？我们需要明白以下两个事实：

一

不同容量的存储器，访问速度差异悬殊。以磁盘和内存为例，访问磁盘的时间大概是ms级的，访问内存的时间大概是ns级的。有个形象的比喻，若一次内存访问需要1秒，则一次外存访问需要1天。所以，现在的存储系统，都是分级组织的。

最常用的数据尽可能放在更高层、更小的存储器中，只有在当前层找不到，才向更低层、更大的存储器中寻找。这也就解释了，当处理大规模数据的时候（指无法将数据一次性存入内存），算法的实际运行时间，往往取决于数据在不同存储级别之间的IO次数。因此，要想提升速度，关键在于减少IO。

二

磁盘读取数据是以数据块(block)（或者：页，page）为基本单位的，位于同一数据块中的所有数据都能被一次性全部读取出来。

换句话说，从磁盘中读1B，与读1KB几乎一样快！因此，想要提升速度，应该利用外存批量访问的特点，在一些文章中，也称其为磁盘预读。