B 树

B 树

• 目录：

  

• 一、卫星数据：
  • 指索引元素所指向的数据记录，比如数据库中的某一行。在B-树中，无论非终端结点还是叶子结点都带有卫星数据；在B+树中只有叶子结点带有卫星数据，其余非终端结点仅仅是索引，没有任何数据关联。
  • 在数据库的聚集索引中，叶子结点直接包含卫星数据；在非聚集索引中，叶子结点带有指向卫星数据的指针。
• 二、B- 树
  • 定义：
    • 一种平衡的多路查找树；
  • 使用场景：
    • 做文件的索引，在文件系统多使用；
  • 结构/特点：
    • 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：
      • 1、树中每个结点至多有m棵子树；
      • 2、若根结点不是叶子结点，则至少有两棵子树；
      • 3、除根之外的所有非终端结点至少有[m/2]棵子树；
      • 4、所有的非终端结点中包含下列信息数据；
        • （n, A, K） n 关键字个数 k 为关键字 A 为指向子树根结点的指针；
      • 5、所有的叶子 结点都出现在同一层次上，并且不带信息（实际上不存在，指向这些结点的指针为空）；
    • 例子：
      • m，阶数是一个节点的子节点数目的最大值。
      • 4阶的B-树，深度为 4：

        

        • 可以看出，有一个头指针，指向根结点；
        • 查找成功，结束；不继续向下；
        • 查找失败，如果顺着指针查找，指针指向叶子结点，则说明该关键字不在此树上。
  • 查找
    • 在B-树上进行查找的过程是一个顺时针查找结点和在结点的关键字中进行查找交叉进行的过程。
    • 在B-树上查找包含两个基本操作：
      • 1、在B-树中找结点；
      • 2、在结点中找关键字。
      • B-树通常存储在磁盘上，前一查找操作是在磁盘上进行的，后以查找操作是在内存中进行的；即在磁盘上找到指针p所指结点后，先将结点信中的信息存储在内存中，然后再利用顺序查找或者折半查找查询等于K的关键字。
    • 决定B-树查找效率的因素：
      • 在磁盘上查找的次数，即待查关键字所在结点在B-树上的层次数。因为在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多。
    • 查找最坏的情况，即待查结点在B-树上的最大层次数。也就是含N个关键字的M阶B-树的最大深度是多少。
• 三、B+ 树
  • • B+ 树是应文件系统所需而出的一种B-树的变型树。
  • 使用场景
    • 为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录结点都是按键值的大小的顺序存放在同一层的叶子结点中，各叶子结点通过指针连接。
  • • m阶的B-树：
      • 1、有n棵子树的结点中包含有n个关键字；
      • 2、所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
      • 3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大(或最小)关键字。
    • • 3阶的B+树

        

        • 从上图得出的结论：
          • 1 、通常在B+树上有两个头指针，一个指向根结点；一个指向关键字最小的叶子结点。
          • 2、叶子结点之间通过指针形成一个有序链表；
      • 单个查找：
  • • 两种查找算法：
      • 1、从最小关键字起顺序查找；
      • 2、从根结点开始，进行随机查找。
• 四、B+ 和B-树，不同的是：
  • 1、若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。（稳定）；B-树查找成功即停止；
  • 2、IO次数更少；
    • B+树的非终端结点没有卫星数据，故相同大小的磁盘页可以容纳更多的结点元素，意味着数据量相同的情况下，B+树的结构比B-树更加矮胖。
  • 3、范围查询更简单；比如（3-9）
    • B-树：查找到叶子结点大于等于3结束；（中序遍历）
    • B+树： 从根结点开始查找到叶子结点大于等于3，然后通过叶子结点的链表进行查找。