数据结构之B树、B+树、B*树_数据结构b加树

1、应用背景

二叉查找树、AVL树、红黑树等都属于二叉树的范围，查找的时间复杂度是Ｏ(log 2N)，与树的深度相关，那么降低树的深度自然会提高查找效率。
但是我们面对这样一个实际问题：大规模数据存储中，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。
因此，为了减少磁盘I/O的次数，必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是：

• 每个节点存储多个元素
• 摒弃二叉树结构，采用多叉树

这样就引出来了一个新的查找树结构 ——多路查找树。根据AVL树给我们的启发，一颗平衡多路查找树可以使得数据的查找效率保证在O(logN)这样的对数级别上。

1.1 机械硬盘结构

为什么树的深度会与磁盘I/O相关呢？这要从硬件层面来说明。
机械硬盘的结构图如下：

硬盘中一般会有多个盘片组成，每个盘片包含两个面，每个盘面都对应地有一个读/写磁头。
每个盘面都被划分为数目相等的磁道，并从外缘的“0”开始编号，具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面。

盘面中一圈圈灰色同心圆为一条条磁道，从圆心向外画直线，可以将磁道划分为若干个弧段，每个磁道上一个弧段被称之为一个扇区。扇区是磁盘的最小组成单元，通常是512字节，不过由于不断提高磁盘的大小，部分厂商设定每个扇区的大小是4096字节。
顺便多说一句，以上图片是老式机械硬盘的示意图，每个磁道的扇区弧长是不一样的。越靠内的磁道密度越大，存储的数据也就越多；越靠外的磁道密度越小，存储的数据也就越少。所以，虽然内外磁道的扇区弧长不一样，由于密度的原因，每个扇区存储的数据量仍然是一样的。然而在新式磁盘中，内外磁道的扇区密度都是相同的，所以新式磁盘每个扇区的弧长都是一样的。

1.2 读写原理

当硬盘驱动器执行读/写功能时，盘片绕主轴高速旋转，当磁道在磁头)下通过时，就可以进行数据的读 / 写了。
系统将文件存储到磁盘上时，按柱面、磁头、扇区的方式进行，即最先是第1磁道的第一磁头（也就是第1盘面的第1磁道）下的所有扇区，然后，是同一柱面的下一磁头，……，一个柱面存储满后就推进到下一个柱面，直到把文件内容全部写入磁盘。
系统也以相同的顺序读出数据。读出数据时通过告诉磁盘控制器要读出扇区所在的柱面号、磁头号和扇区号（物理地址的三个组成部分）进行（目前多是通过LBA线性寻址的方式定位）
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费（磁盘旋转和磁头移动），磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数