您所在位置：网站首页 > 机械/制造/汽车 > 综合/其它B+树的组织结构

B+树的组织结构

2页

卖家[上传人]：大米

文档编号：491530231

上传时间：2023-09-20

文档格式：DOCX

文档大小：58.26KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 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的一个文件记录或一个指针（存储）桶，桶中的每个指针指向具有搜索码值Ki的一个文件记录。指针桶只在文件不按搜索码顺序物理存储时才使用。指针Pn具有特殊的作用；每个叶结点最多可有n-1个搜索码值，最少也要有（旷个搜索码值。各个叶结点中搜索码值的范围互不相交。要使B+树索引成为稠密索引，数据文件中的各搜索码值都必须出现在某个叶结点中且只能出现一次；由于各叶结点按照所含的搜索码值有一个线性顺序，所以就可以利用各个叶结点的指针Pn将叶结点按搜索码顺序链接在

2、一起。这种排序能够高效地对文件进行顺序处理，而B+树索引的其他结构能够高效地对文件进行随机处理，如图8-3-2所示。图8-3-2： B+树索引的叶结点结构示例H文件按搜索蹈艄序軸理存储Brighton 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+树索引结构

《B+树的组织结构》由会员大米分享，可在线阅读，更多相关《B+树的组织结构》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源