索引之B-TREE定义及约束

B-tree的特点:

  1、节点至少包括两个孩子

  2、树中每个节点最多含有m个孩子 m>=2

  3、除根结点及叶子节点外每个节点最多含有ceil(m/2)个孩子

  4、所有的叶子节点都位于同一层

假设每个非终端节点中包含n个关键字信息,其中

  a、Ki(i = 1~n)为关键字,且关键字按顺序升序排排序,即 ki>k(i-1)

  b、关键字的个数n必须满足【ceil(m/2-1) <=n<=m-1

  c、非叶子节点的指针 P[1 ]P[2] P[m],P[1]指向关键字小于K1的子树,P[m]指向K[m-1]的字数,P[i]指向关键字属于(K[i-1]到K[i])的子树。

B+-tree的特点:

B+树是B树的变体,基本定义与B树相同,区别点在于如下:

  1、非叶子节点的子树指针与关键字个数相同(B+Tree能存储更多的关键字)

  2、非叶子节点的子树指针P[i]指向关键字[Ki-Ki+1)的子树

  3、非叶子节点仅仅用来做索引,数据都保存在叶子节点中

  4、所有的叶子节点均有一个链指针,指向下一个叶子节点(范围统计)

结论:B+tree更适合做存储索引,理由如下:

  1、B+tree的磁盘读写代价更低

  2、B+树的查询效率更稳定

  3、B+树更有利于对数据库的扫描

原文地址:https://www.cnblogs.com/niuyg928/p/15144720.html