@@ -1,58 +0,0 @@ B+TREE索引的优势 | 凤凰涅槃进阶之路

B+TREE索引的优势

Abel sun2022年12月24日
约 1350 字大约 5 分钟

B+TREE索引的优势

1. 影响索引查询效率的主要原因

  1. 索引存储在磁盘上

    索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储在磁盘上

  2. 磁盘I/O存取慢

    索引在查找过程汇总要产生磁盘I/O消耗,相对于内存存储,I/O存储的消耗要高几个数量级

所以索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数,提升索引效率

2. 为什么磁盘存储慢

2.1 磁盘存取原理

索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O 操作,与主存不同,磁盘I/O存在机械运动耗费。因此磁盘I/O的时间消耗时巨大的

image-20210207165425148

2.1.1 磁盘的组成

  • 一个磁盘由大小相同且同轴的圆形盘片组成

    磁盘可以转动(各个磁盘必须同步转动)。

  • 在磁盘的一则有磁头支架

  • 磁头支架固定了一组磁头

    • 每个磁头负责存储存取一个磁盘的内容

    • 磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动)

    • 每个磁头同一时刻必须是同轴的

2.1.2 磁盘组成和工作原理

image-20210207165434956

  • 磁道

    每个同心环叫做一个

  • 扇区

    磁盘的最小存取单元

2.1.2.1 确定数据位置

当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址。既确定要读的数据在哪个磁道,哪个扇区

2.1.2.2 磁头寻道

为了读取这个扇区的数据,需要将磁头放在这个扇区上方,为了实现这一点,磁头需要移动对准响应的磁道,这个过程叫做寻道,所耗费的时间叫寻道时间,

2.1.2.3 磁盘旋转到对应扇区

然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间

3. 磁盘局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存储就比主存慢很多,在加上机械运动耗费,磁盘的存取速度往往是主存的几百分之一,因此为了提高效率,要尽量减少磁盘I/O,为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存,预读可以提高I/O效率预读的长度一般为页(page:计算机管理存储器的逻辑块-通常为4k)的整数倍。主存和磁盘以页为单位交换数据。当程序要去读的数据不再主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中

4.B-/B+Tree索引的优势

一般使用磁盘的I/O 次数评价索引优势

那么BTree如何减少磁盘次数的呢

  1. 结合操作系统存储结构优化处理:MySQL巧妙运用操作系统存储结构**(一个节点分配到一个存储页中->尽量减少I/O操作)&磁盘预读(缓存预读->加速预读马上要用到的数据)**

    • 详解:

      Mysql设计利用了磁盘预读原理,将一个b+tree节点大小设为一个页大小,在新建节点时直接申请一个页的控件,这样就能保证一个节点物理上存储在一个页里,加之计算机存储分配都是按页对其,这样就实现了每个Node节点只需要一次IO操作

  2. B+Tree单个节点能放多个子节点,相同IO次数,检索出更多东西 这也是B+Tree相比B-Tree能查询出更多数据的原因

    • 详解

      单个节点能放多个子节点,查询IO次数相同(mysql查询IO次数最多3-5次-所以需要每个节点需要存储很多数据)

  3. B+Tree只在叶子节点存储数据&所有叶子节点包含一个链指针&其他内层非叶子节点只存储索引数据,只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据

  • B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

  • B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。

    dmax=floor(pagesize/(keysize+datasize+pointsize))

评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.9.1