b-tree
其中b代表“balanced”（平衡）。
我们使用磁盘时，主要瓶颈在于磁盘i/o。磁盘读取数据是按块（block）进行的，通常一个块的大小是4kb。如果我们用传统的二叉树（比如二叉搜索树）来存储大量数据，每个节点只存储一个键和两个指针，那么依次磁盘i/o只能读取一个节点，树的高度会很高，导致需要多次磁盘i/o。 b树的设计就是为了减少磁盘i/o次数。它的一个几点可以存储多个键和多个子节点指针，这样一次磁盘i/o可以读取一个节点（包含多个键和多个指针），然后在这个节点内部进行内存中快速查找，从而减少树的高度和磁盘i/o次数。 通俗来说，b树是一种多路搜索树，每个节点有多个子节点。它通过以下方式工作： 1、节点可以包含多个键，这些键将数据划分成多个区间，每个区间对应一个子节点。 2、所有叶子节点都在同一层，这样保证了树的平衡，即从根到叶子节点的路径长度相同。 在磁盘上，b树的一个节点通常设计成刚好一个磁盘块（或几个块）的大小，这样一次磁盘读取就可以把一个节点的所有数据读入内存。节点内部存储的键和指针的数量根据节点的大小和键、指针的大小来计算。 例如，假设一个磁盘块是4kb，一个键是4字节，一个指针式8字节，那么一个几点最多可以存储的键的数量n满足：4n+8(n+1)<=4096（这里假设节点结构为：n个键，n+个指针）。解这个不等式，得到n大约为340.也就是说，一个几点可以有340个键和341个指针。这样，一颗三层高的b树可以存储的数据量大约是：根节点有340个键，第二层有341个节点，每个节点有340个键，第三层（叶子节点）有341*341个节点，每个几点有340个键，总共大约340*341*340≈三千九百万个键。而只需要3次磁盘i/o（根节点、第二层某个节点、叶子节点）就可以找到任何一个键。 这就是b树在磁盘上高效地原因：通过增加每个节点的分支树，降低树的高度，从而减少磁盘i/o次数。b-tree比喻
b树的工作方式比如（索引查找）： 1、读书馆门口有个总目录（根节点）：“A-L在1楼，M-Z在2楼” 2、到1楼看到分目录：“A-C在1-10架，D-F在11-20架” 3、到具体书架看到：“D开头的在1-5排，E开头在6-10排” 4、最后在一排书种快速找到你想要的那本。磁盘的特性
磁盘的工作原理（机械硬盘）： 1、磁头需要移动到正确的磁道。此过程称为寻道（seek），在整个数据读取过程中占用时间较多。平均寻道时间统称为几毫秒。（例如：3-15ms） 2、等待盘片旋转到正确位置。此过程称为旋转等待（rotational latency），这个时间称为旋转等待时间，取决于磁盘转速。例如对于7200 RPM的从盘，旋转一周的时间为60/7200=8.33ms，平均旋转等待时间为半周，即4.17ms。 3、当目标山区转到磁头下方是，开始读取数据。数据传输时间取决于数据量和磁盘的数据传输速率。例如，假设数据传输速率为100mb/s，读取一个扇区（512b）的时间约为0.005ms。 磁盘的概念： 1、基本结构： 盘片（platter）：一个而硬盘通常包含一个或多个盘片，每个盘片有两个表面（上下），通常每个表面都会用来存储数据。盘片由硬质材料制成，表面涂有磁性材料。 磁头（head）：每个表面都有一个磁头，用于读写数据。磁头安装在磁头臂上，可以沿着盘片半径方向移动。 主轴（spindle）：盘片固定在主轴上，有电机带动旋转。 2、数据组织方式： 磁道（track）：当盘片旋转时，磁头在盘片表面画出的原型路径称为磁道。每个盘片表面有成千上万个通信磁道。 柱面（cylinder）：不同盘片上相同半径的磁道组成一个柱面。柱面的数量等于每个盘面的磁道数。使用柱面可以避免磁头移动，因为同一柱面上的并不同盘面的数据可以通过切换磁头来读取，而不需要移动磁头臂。 扇区（sector）：每个磁道被划分成多个扇区，每个扇区通常存储512字节（现代硬盘可能使用4kb扇区）。扇区是磁盘读写的最小单位。 3、寻址方式 chs寻址（cylinder-head-sector）：早期使用，通过柱面号、磁头号、扇区号来定位数据。 LBA寻址（logical block addressing）：现代磁盘使用，将整个磁盘的扇区从0开始编号，操作系统通过逻辑块地址（一个整数）来指定扇区。 B树比二叉树的优点： 读取1字节和4kb时间差不多，就一次夺取一个块，一个块里面尽可能的多放数据。b-tree工作步骤
1、查找过程
从根节点开始查找，在这个节点内快速查找，例如要找到35，比40大，比25小——>走25-40之间的路。再继续去而二层节点内快速查找，直到找到，返回数据。如果走到了叶子节点还没找到，则判断为数据不存在。2、插入过程
1、当块中还有空位时，直接插入并保持有序 2、当数据块中无空位时，需要分裂。 把块中所有内容以及新数据排序，找到中间位置，分成两个数据块，把中间键返回给父节点。如果父节点也满了，继续向上分裂。这可能一直传递到根节点，导致树长高了一层。3、删除过程
找到要删除的键，如果是叶子节点，直接删除，检查是否数据块内存储内容太少（少于半满），如果太少，需要向邻居借，如果做邻居的块大于半满，就向左邻居借一个，如果右邻居的块大于半满，就向右邻居借一个，如果左右两边都“穷”，合并节点。
