20. B+树

1. B+树

B+树是B树的变体，常用于数据库和操作系统的文件系统中，MySQL数据库的索引就是基于B+树实现的
B+树的特点
1. 分为内部节点（非叶子）、叶子节点2种节点
2. 内部节点只存储key，不存储具体数据(B树两者都存)
3. 叶子节点存储key和具体数据(图中的Q)
4. 所有的叶子节点形成一条有序链表(B树没有)
5. m阶B+树非根节点的元素数量 x，┌ m/2 ┐ ≤ x ≤ m(B树中节点元素数量，最多是m-1，最少是┌ m/2 ┐-1)
硬盘的分类
1. 机械硬盘（Hard Disk Drive，HDD）
2. 固态硬盘（Solid State Drive，SSD）
磁盘相关概念
1. 硬盘一般由多个盘片组成
2. 每个盘片包含2个盘面
3. 每个盘面有1个对应的读写磁头，盘面、磁头由上到下从0开始编号
4. 盘面中的一圈圈灰色圆环为是一条条的磁道，磁道由外到内从0开始编号
5. 每条磁道上的一个弧段叫做一个扇区，扇区是磁盘的最小读写单位，一个扇区的大小通常是512字节，也有4096字节的
6. 相同编号的磁道形成一个圆柱，称为柱面，磁盘的柱面数与一个盘面的磁道数是相等的
早期硬盘的扇区细节
1. 每条磁道的扇区数相同，所以外圈扇区的面积会比内圈扇区大
2. 为了更好的读取数据，它们会存放相同的字节数，所以外圈扇区的记录密度要比内圈小，会浪费大量的存储空间
3. 硬盘的存储容量 = 磁头数 * 盘面磁道数 * 磁道扇区数 * 扇区字节数
磁盘块
1. 磁盘块，在Windows中叫做簇（cluster），在Linux中叫做块（ block ）
2. 相邻的 2 ^n 个扇区组合在一起，形成一个磁盘块
3. 操作系统对磁盘进行管理时，以磁盘块作为最小读写单位
4. 一般一个磁盘块是4096字节（4KB，由8个连续的512字节扇区组成），所以有时，你创建一个空文件，也至少是4字节
5. 磁盘块是操作系统中的一个虚拟概念，扇区是磁盘上真实存在的物理区域
操作系统读取硬盘数据的过程
1. 操作系统将逻辑块地址(LBA（Logical Block Address)，例如设备号4(可能表示磁盘或U盘)、磁头号4、磁道号8、扇区号16、扇区计数8），传送给磁盘驱动器并启动读取命令
2. 磁盘驱动器根据LBA将磁头移动到正确的磁道，盘片开始旋转，将目标扇区旋转到磁头下
3. 磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区
4. 磁盘驱动器向操作系统发出“数据就绪”信号
5. 操作系统从磁盘界面的缓冲区读取数据
  1. 既可以按照一个字节一个字节的方式读取
  2. 也可以启动DMA（Direct Memory Access，直接内存访问）命令读取
磁盘完成IO操作的时间，主要由寻道时间、旋转延迟时间、数据传输时间3部分构成
1. 寻道时间（seek）：将读写磁头移动至正确的磁道上所需要的时间，这部分时间代价最高
2. 旋转延迟时间（rotation）：盘片旋转将目标扇区移动到读写磁头下方所需要的时间，取决于磁盘转速
3. 数据传输时间（transfer）：完成传输数据所需要的时间，取决于接口的数据传输率，通常远小于前两部分消耗时间
决定时间长短的大部分因素是和硬件相关的，但所需移动的磁道数是可以通过操作系统来进行控制的
1. 减少所需移动的磁道数是减少整个硬盘读写时间的有效办法
2. 合理安排磁头的移动以减少寻道时间就是磁盘调度算法的目的所在
MySQL的存储引擎InnoDB的最小读写单位是16K原因
1. 操作系统每次至少读取一个磁盘块，也就是4096字节
2. 因此不能将节点设计太小，设计太小会导致需要频繁的进行IO操作
3. 一般把一个节点的大小设计成最小读写单位的大小，而MySQL中最小16K
MySQL的索引底层使用B+树而不使用B树原因
1. B树必须同时存key和value，而B+树的非叶子节点可以只存key，因此同样16k大小的节点，B树存储的key更多，树的高度也就越低，存放的B+树阶数要远高于B树的阶数
2. B+树的value都在叶子节点上，所以每次查询都要查到叶子节点，而根节点到叶子节点步骤是相同的，因此查询速度比较稳定，而B树，可能查到第二层就找到了具体数据
3. 所有的叶子节点构成了一个有序链表，做区间查询时更方便，例如从5到20，那么直接查到5，然后通过5对应的节点，一路往右，查到20停止即可，无需再从根开始查，对于B树，需要中序遍历，非常麻烦

2 B*树

B*树是B+树的变体：给内部节点增加了指向兄弟节点的指针
如果m阶B*树非根节点的元素数量 x，那么┌ 2m/3 ┐ ≤ x ≤ m

1. B+树

2 B*树

相关推荐