B+树的组织结构

《B+树的组织结构》由会员分享，可在线阅读，更多相关《B+树的组织结构（2页珍藏版）》请在金锄头文库上搜索。

1、B+树的组织结构2007-12-05 09:03B+树的组织结构1、B+树索引的总体结构 B+树索引是一个多级索引，但是其结构不同于多级顺序索引； B+树索引采用平衡树结构，即每个叶结点到根的路径长度都相同； 每个非叶结点有至血个子女，n对特定的树是固定的； B+树的所有结点结构都相同，它最多包含n-1个搜索码值K、Kn-1，以及n个指针P2、Pn， 每个结点中的搜索码值按次序存放，即如果vj,那么KivKj,如图8-3-1所示。图8-3-1： B+树的结点结构2、B+树索引的叶结点 指针Pi（i=l,2,.,n-1）指向具有搜索码值Ki的一个文件记录或一个指针（存储）桶，桶中的每个指针指向具

2、有 搜索码值Ki的一个文件记录。指针桶只在文件不按搜索码顺序物理存储时才使用。指针Pn具有特殊的作用； 每个叶结点最多可有n-1个搜索码值，最少也要有（旷个搜索码值。各个叶结点中搜索码值的范围互不相交。要使B+树索引成为稠密索引，数据文件中的各搜索码值都必须出现在某个叶结点中且只能出现一次； 由于各叶结点按照所含的搜索码值有一个线性顺序，所以就可以利用各个叶结点的指针Pn将叶结点按搜索码顺序链接在一起。这种排序能够高效地对文件进行顺序处理，而B+树索引的其他结构能够高效地对文件进行 随机处理，如图8-3-2所示。图8-3-2： B+树索引的叶结点结构示例H文件按搜索蹈艄序軸理存储Brighto

3、n Dcwfxi IA-S17.viol750500600了 00BrightonDowiitoh3、B+树索引的非叶结点 B+树索引的非叶结点形成叶结点上的一个多级（稀疏）索引； 非叶结点的结构和叶结点的结构相同，即含有能够存储n-1个搜索码值和n个指针的存储单元的数据结构。只 不过非叶结点中的所有指针都指向树中的结点； 如果一个非叶结点有m个指针，贝则mn。若mvn,贝U非叶结点中指针Pm之后的所有空闲空间作为预留空间，与叶结点的区别在于结点的最后一个指针Pm和Pn的位置与指向不同，如图8-3-3所示；图8-3-3： B+树索引的非叶结点结构P V -V as 在一个含有m个指针的非叶结点中，指针P(i=2,m-1)指向一棵子树，该子树的所有结点的搜索码值大于等 于Ki1而小于。指针Pm指向子树中所含搜索码值大于等于Km1的那一部分，而指针P/旨向子树中所含搜索码 卜Iim-iI值小于匕的那一部分，如图8-3-4所示。图8-3-4： B+树索引的非叶结点中指针Pi的指向4、B+树索引的根结点 根结点的结构也与叶结点相同； 根结点包含的指针数可以小于。但是，除非整棵树只有一个结点，否则根结点必须至少包含两个指针。图8-3-5给出一个B+树结构的示意图。图8-3-5： account关系的B+树索引结构