换个角度，看看B树和B+树

换个角度.jpg

在学习数据结构的时候，往往学习的思路是直奔主题，学习各种大神们设计出来的结构精妙的数据结构。但是，这样的学习方式使各个结构在脑中形成了一个个孤岛，没有什么联系。

如果换个角度，从问题入手，看看为了解决特定的问题，我们需要什么样的数据结构来更好地解决问题，在一步步解决问题的过程中，看看结构之间的联系是怎么样的，这样的学习效果会不会好一些？

现在就来试一试，从解决查找问题为切入点，延伸到B树，B+树。

问题是什么？

从计算机诞生以来，数据就未曾离开过计算机。人类与计算机交互所产生的输入、操作系统、运行在操作系统上的软件、软件处理的业务信息，这些都是数据，而计算机的运行过程就是对各种数据做计算的过程。这时问题就来了，计算机要处理的数据从何而来？

如何看待存储设备

数据存储在存储设备中，比如内存、硬盘。

先看看内存。

内存从结构上来看，像是一个由点组成的矩阵，行的长度是8，宽度则视内存大小而定，每个点是一个bit，存储着0、1值。一行由8个点组成，即一行是8bit，即1byte。

CPU访问内存的方式是通过内存地址，每个内存地址指向的bit都是位于矩阵的第一列的bit，并且一次对内存的访问会获取8bit(1byte)或16bit(2byte)或32bit(byte)等等，即获取8n bit(n byte)，n值由CPU位数决定。

根据CPU对于内存的访问方式，可以把上边所说的由点组成的矩阵，抽象成由 地址-数据 两列组成的表，通过一个内存地址，就能获取到相对应的数据。

再看看磁盘。

磁盘中的数据存储在多张盘片上，每张盘片以圆心为轴，划分为多个磁道，每个磁道上等距离的分布着多个点，点中记录着0、1信号。因此要访问磁盘中的某个bit数据，需要指定在哪张盘片、哪个磁道、哪个位置。能不能通过抽象来简化对磁盘的访问？这样尝试一下，把每个盘片以圆心为轴分割成多个扇面，每个扇面512Byte，再把每个盘片的每个扇面按顺序编上序号，这样访问磁盘的方式就变成了通过一个扇面编号，就能获取到相对应的512byte数据，即抽象成了由 扇面标号-数据 两列组成的表。

无论是内存，还是磁盘，对数据的访问都可以抽象成一张表，表的第一列是我们取得数据需要的凭证，第二列是对应的数据。

我们可以认为，这就是数据结构中所说的线性结构，属于最基本、最原始的结构。所以无论是访问内存、还是访问磁盘，我们都认为是对线性结构的访问。

下边把内存、磁盘中的数据统称为线性结构。

如何从线性结构找到想要的数据

完成了上边的抽象，我们开始考虑一个问题：假设在线性结构中存储着数据A，我们想通过数据A的标识来找到它，该怎么做？

1. 顺序遍历

最简单的方式，就是对线性结构从头到尾的找，看看哪个数据是我们要的数据。

顺序遍历.png

这个方式简单可行，很容易就达到了目的。

这时出现了一个新的问题，如果线性结构的长度越来越长，用上边的方式会怎样？

顺序遍历2.png

如果目标数据位于第1000项，我们需要比较1000次标识才能找到，也就是说有999次无意义的比较，尤其是在线性结构长且目标数据位于偏后的位置时。

既然这样，那可不可以避免无意义的比较来提高查找的效率？

2. 哈希表

现在尝试着在线性结构之外构造一个新的结构--哈希表，这个结构能够根据要查找的数据，直接定位到数据的位置，从而提高查找效率。

哈希表.png

这次，不管数据有多少，我们能够用1次计算就能找到数据A了，在效率上不能更快了！

这里对哈希表做了简化，实际上会有哈希冲突的问题，这个问题会影响查找的效率，影响程度取决于哈希表的宽度和哈希算法的离散程度，这里不展开讨论。

不过还是存在着问题。哈希表与线性结构是一一映射的关系，这就代表了哈希表的大小会随着线性结构的增大而增大，这在线性结构很大的情况下是一笔不小的空间开销。也就是说，哈希表是一种用空间换时间的策略。

那么，下一个问题来了：在不牺牲空间的前提下，能不能得到一个较高的查找效率？

3. 二叉查找树

想要不牺牲过多的空间，同时还要得到比顺序遍历更高的查找效率，这就代表着我们得让线性结构本身具备某种线索能够引导我们找到目标的数据。所以我们把线性结构构造成树结构：

构建二叉搜索树.png

构建后的结构不够直观，用树形表示看下：

二叉搜索树.png

可以看到，在构建后的二叉搜索树中查找数据A的过程进行了3次比较，而用顺序查找的方式是3次比较，效率确实提高了些，但是看上去提高的不明显。我们对顺序查找和二叉搜索树查找的效率进行量化看看。

假设数据量为n。

对于顺序查找，最好的比较次数是1，即第一个就是目标数据；最坏的比较次数是n，即最后一个是目标数据。那么平均查找次数 = (n+1)/2 ≈ O(n)

对于二叉搜索树，最好的比较次数是1，即根节点是目标数据；最坏的比较次数是log(n+1)，即根节点是叶子节点。那么平均查找次数 = (log(n+1) + 1)/2 ≈ O(logn)

其实二叉搜索树的最坏比较次数是n，也就是当树被构建成只有左子树或者右子树的时候，这里就不讲树的平衡了，把注意力都放在主要的思路上。所以，我默认构建出来的树都是平衡二叉树，下文也是一样。

时间复杂度.png

看看两种查找的时间复杂度曲线，由此看出，当数据量大的时候，二叉搜索树的平均查找效率高于顺序查找，因此此结构可以满足不牺牲空间同时还能提高查找效率的需求。

我们仍然能在这个方案上发现问题。假设线性结构的数量极大，内存空间已无法容纳，那么我们就不得不在磁盘中来存储这份数据。这时问题来了，如果要在存储在磁盘中的二叉搜索树里查找数据，需要平均访问logn次磁盘（由上文的时间复杂度得出），比如n=100k，则一次查找要平均访问磁盘17次，这个很要命，要知道读取机械硬盘的时间是几十毫秒的级别，即使是SSD也得是几十微秒，这和读取内存的纳秒级别的速度差距非常大。因此，在这种情况下，硬盘的读取速度导致了二叉搜索树的查找速度非常缓慢。

既然硬盘的读取速度是效率的瓶颈，那么能不能找到某种方式，通过减少读取硬盘的次数来提高效率？

B树

在二叉搜索树中查找数据，每向下遍历一层，则需要多访问一次磁盘。那么，可以通过减少树的深度来减少读取磁盘的次数。

我们在二叉搜索树的基础上，拓展一下每个节点，即让每个节点从只能存储一份数据，拓展到最多存储两份数据。这样每个节点能够存储1份或2份数据，所以每个节点长度不一定相等，需要通过指针来指向下一个节点，这个就是B树。

2-3树.png

可以看出来，拓展之后的树的深度比原来少了1，所以最坏的情况下比较次数比原来少了1次，达到了减少访问磁盘次数的目的。

那我们猜想一下，如果再扩展每个节点的数据，拓展成3份、4份....m份，那么节点会越来越宽，树的深度会越来越小。

假设我们构建了一棵每个节点存储8份数据、深度为3的B树，那么深度为1的节点有1个，总共存储了1*8=8份数据；深度为2的节点有1*(8+1)=9个，总共存储了9*8=72份数据；深度为3的节点有9*(8+1)=81个，总共存储了81*8=680份数据。综上，总共可存储8+72+680=760份数据。也就是说我们对这760份数据做查找最多访问磁盘3次，和上边说的存储了7份数据的搜索二叉树持平。

为了达到效率最优，B树的节点大小往往被设置成与磁盘扇区大小一致，一般为512。因为一般读取磁盘的单位是扇区，这样的设置充分利用了每次对磁盘的读取，从而减少读取次数。

B树解决了磁盘读取过多导致查找效率低的问题，但它存在着查找之外的其他问题：如果我们想按顺序遍历一遍所有数据，需要怎么做？以上面的图为例，遍历A->B->C->D->E->F，这个过程中访问了两次B和F所在节点。也就是说非叶子节点需要访问多次，这样并不理想。

那么，有什么办法能在满足B树特性的前提下还可以高效的顺序遍历所有数据？

B+树

把B树节点中的数据都放到叶子节点中，而非叶子节点中只保留标识和指针，看看结构是什么样的：

B+树.png

它依然保留着B树的特性，同时还有些不同。B+树只有遍历到了叶子节点才能获取到数据，非叶子节点中只有标识信息，这导致查找的效率变低了，但这换来的是所有数据都集中在了叶子节点中，从而能够按顺序串联在一起，实现高效的遍历。

总结

本文从对存储设备中的数据做查找的问题开始讨论，一步步找到解决方案，同时发现新的问题，如此往复直到延伸到B+树。这里没有讨论具体的细节，比如如何解决哈希冲突、如何构建平衡二叉树等等，我希望把注意力放在在发现问题和解决问题的过程中，在这个过程中逐渐衍生出新的结构，并用这些结构来解决特定的问题，从而对这些结构能有个新的认识。

这里只涉及了小部分的数据结构和查找这一个问题域，其他的结构和问题还有很多，我相信也可以通过这种形式来思考一下，也许也会有同样新的认识。

如果本次的讨论有那些不严谨的地方，希望发现的人能帮我纠正一下，算是对我的帮助吧。

欢迎交流~