前言
本文的重点不是B树、B+树和索引的性质、使用等，而是三者之间的关系。
为了便于说明，我们先定义一条数据记录为一个二元组[key,data]，key为记录的键值，key唯一；data为数据记录除key外的数据。
B树
B树示意图
红色部分称为一个结点。每个结点都存储key和data，所有结点组成这棵树，并且结子节点指针为null。
B+树
B树示意图
B+树结点的定义与B树一样。只有叶子结点存储data，叶子结点包含了这棵树的所有键值，叶子结点不存储指针。
上面概括地介绍了B树和B+树的特点，它们详细的性质和增删查改可以百度，不是本文重点。
索引
红色部分就是索引
数据库以二维表的形式存储，如果我们以某一属性或多条属性为条件查找时，如果没进行查询优化，那么就只能从头开始顺序查找，效率极低。所以我们可以建立索引（是一种数据结构）来帮我们快速定位（该数据结构的查询速率快于顺序查询）到某个地址来找到某一行，以此来优化查询。常见的索引结构有B树、B+树、哈希表。
我们知道数据表其实是存储在存储器中的，一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。当我们要查询时就需要先去存储器中读取索引，通过索引去快速定位数据。这就意味着索引查找过程中就要产生磁盘I/O消耗。
相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。在这之前，我们要知道磁盘存取原理
磁盘存取原理
磁盘原理图
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路会确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做
寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
显然寻道和旋转都属于机械运动，因为机械运动的时间远大于电子运动的时间，所以磁盘读取远慢于内存读取（内存读取是电子运动）。所以我们可以通过提高寻道定位的效率（磁盘预读）来达到磁盘存取优化。
磁盘预读
程序运行期间所需要的数据通常比较集中，当一个数据被用到时，其附近的数据也通常会马上被使用。这就是著名的局部性原理。
所以，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。那么假如你第一次只需要A区域的1个字节数据，然后就定位到其他区域去读取数据，当你过了一会又需要A区域的数据，就不用重新定位到A区域读取了，因为已经在第一次读取A区域时预读了。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
为什么采用B/B+树做索引，而不是二叉查找树做索引？
根据B/B+树的定义，可知检索一次最多需要访问h（深度）个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（每次新建节点时，直接申请一个页的空间），这样每个节点只需要一次I/O就可以完全载入。而B/B+树一个结点又可以存储多个数据，这使得它们与普通的二叉树相比减少了结点个数和树的深度（简要来说就是变得胖矮了），这样会减少磁盘的I/O操作次数，增大索引结构效率。
既然B树能增大索引结构效率，为什么还要B+树？
从上面可以知道一个结点设置成一个页的大小，使每个结点一次I/O就可以完全载入。那么因为B+树只有叶子结点存储data，非叶子结点只存储key。那么一个页的大小就能存储更多的key，而我们查找只需要key，这就会使得B+树更胖更矮。由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，
所以：B+树更适合当数据库索引，B树更适合当文件索引。因为文件夹中存储着data,而不单单是key。
网友评论