B+树

in 软件 with 1 comment

前言

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树,但它们在降低磁盘I/O操作数方面要更好一些。现在许多数据库系统使用B树或者B树的变种(B+树和B树)来存储信息。B+树是B树的一种变形,它把所有的数据都存储在叶节点中,内部节点只存放关键字和孩子指针,因此最大化了内部节点的分支因子,所以B+树的遍历也更加高效(B树需要以中序的方式遍历节点,而B+树只需把所有叶子节点串成链表就可以从头到尾遍历)。
B+树的图示
B+树示意图

定义

  1. 根结点只有1个,分支数量范围[2,m]。

  2. 除根以外的非叶子结点,每个结点包含分支数范围[[m/2],m],其中[m/2]表示取大于m/2的最小整数。

  3. 所有非叶子节点的关键字数目等于它的分支数量。

  4. 所有叶子节点都在同一层,且关键字数目范围是[[m/2],m],其中[m/2]表示取大于m/2的最小整数。

  5. 所有非叶子节点的关键字可以看成是索引部分,这些索引等于其子树(根结点)中的最大(或最小)关键字。例如一个非叶子节点包含信息: (n,A0,K0, A1,K1,……,Kn,An),其中Ki为关键字,Ai为指向子树根结点的指针,n表示关键字个数。即Ai所指子树中的关键字均小于或等于Ki,而Ai+1所指的关键字均大于Ki(i=1,2,……,n)。

  6. 叶子节点包含全部关键字的信息(非叶子节点只包含索引),且叶子结点中的所有关键字依照大小顺序链接(所以一个B+树通常有两个头指针,一个是指向根节点的root,另一个是指向最小关键字的sqt)。

Responses
  1. Victor

    厉害厉害

    Reply