数据结构课件-B＋树的结构

上传人：P*** IP属地：湖南上传时间：2023-09-10 格式：PPT 页数：5 大小：164.50KB 积分：3.6 举报 版权申诉

全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

B＋树索引是一个多级索引(1)B＋树结点结构P1

…

Pn-1

Kn-1

有n-1个搜索码K1、K2

、…、Kn-1，n个

指针P1、…、Pn。

结点中码值有序存放：如果i<j,则Ki

<Kj

。B＋树的结构(2)叶结点结构，对于i=1,2,…，n-1。指针Pi指向具有Ki的一个文件记录（主索引文件按照码值存放）或指向一个指针桶（辅助索引），桶中每个指针指向具有码值Ki的一个文件记录。指针Pn

指向下一个叶结点的头指针。这样可以将叶结点按照码值顺序串在一起，以便对文件进行顺序处理。叶结点中最多有n-1个码值，至少有

(n-1)/2

个码值，各叶结点中值地范围互不相交，即若Li和Lj

是两个叶结点且i<j，那么Li中的所有码值都小于Lj中的所有码值。要使B＋树索引成为稠密索引，各码值必须出现在叶结点中。(3)B＋树的非叶结点，形成叶结点上的一个多级（稀疏）索引。对于i=2,3,…，n-1，指针Pi指向一棵子树，该子树中所有结点的索引码值大于等于Ki－1且小于Ki

，Pn指向的子树中所有码值大于等于Kn-1，P1指向子树中的所有码值均小于K1。非叶结点中至少有

n/2

个指针，最多有n个，指针个数称为该结点的扇出。(4)根结点：根结点的指针数可以小于

n/2

。

除非整棵树只有一个结点，否则，根结点至少有两个指针。完整的B＋树。如图：

有两种方法:

一、从最小码值起顺序查找;

二、从根结点开始，进行随机查找。随机查找:从根开始(查找长度小于

人人文库> 全部分类> 教育资料 > 课件下载

1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。