B-Tree

作者: edolovee | 来源:发表于2018-03-15 09:32 被阅读0次

    定义

    B树是一个多路的平衡查找树,所谓多路就是多叉,它是一种专门为磁盘等外置存储设备而设计的一种数据结构

    一颗m阶的B树(m叉树或者m路树)满足如下性质:

    1. 每个节点最多包含m个孩子(m>=2)
    2. 除根节点和叶子节点外,其它每个节点至少有ceil(m/2)个孩子
    3. 若根节点不是叶子节点,至少有两个孩子
    4. 所有叶子节点都出现在同一层
    5. 每个非叶子节点包含n个关键字信息(P1,K1,P2,K2...,Kn-1,Pn),其中K(1 - n-1)为顺序排列的关键字,P(1-n)为指向子节点的指针,并满足P(i-1)子树所有关键字<= Ki <=P(i+1)子树所有关键字

    例子

    3路B树


    image.png
    1. 查找
      以查找79关键字为例
    • 从磁盘读取磁盘块1,79 > 35 所以,数据在P3指向的子节点里
    • 从磁盘读取磁盘块4,65 < 79 < 87,数据在P2指向的子节点里
    • 从磁盘读取磁盘块10,遍历即可找到79

    可以看到磁盘IO的次数明显降低,我们知道默认InnoDb存储引擎每个页大小为16KB,而一个关键字信息加上指针信息一般为16B,但是每个关键字还包含着对应的记录的信息,这部分大小不定,可知InnoDb一次读取的磁盘块大概包含16KB/(16B+未知大小),存储的关键字不多,所以也就导致深度会增加,因此InnoDb索引的存储使用的另外一种结构B+Tree

    1. 插入
      生成从空树开始,从一个空节点插入m-1个关键字,当关键字数大于m-1时,则进行分裂,分裂方式是将中间节点升级为父节点,左右分别形成单独节点,依次重复上述步骤

    相关文章

      网友评论

          本文标题:B-Tree

          本文链接:https://www.haomeiwen.com/subject/eyttqftx.html