- 浏览: 169496 次
- 性别:
- 来自: 广州
博客专栏
-
TCP/IP详解卷一>阅读...
浏览量:12550
文章分类
最新评论
-
master11:
你好,博主看完你的解释,好厉害啊!!佩服。如果想运行看一下效果 ...
数独人工解法的一些技巧及其python实现 -
evasiu:
chenxun1012033254 写道lz这么辛苦我也是醉了 ...
数独人工解法的一些技巧及其python实现 -
chenxun1012033254:
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
数独人工解法的一些技巧及其python实现 -
xuyfiei:
lz很厉害,现在该是毕业了吧
恨毕业--读研一年总结 -
nphoenix:
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後,你就會發現個 ...
恨毕业--读研一年总结
转眼又七月份了。6月份后来就变成考试月了。因为图论要求写阅读报告,某天看数据库的空间索引时,又正好看到关于基于树的一些索引技术,于是产生了以此为主题写份阅读报告的想法。今天算是完成了。总共介绍了5种树,二分查找树、AVL树、2-3树、B树及其变种B+树。B+树是现在运用最多的基于磁盘的索引方法。我打算等考完试再把这些树实现一下。以下是我的阅读报告,主要参考Clifford A. Shaffer的《数据结构与算法分析》。
基于树的索引结构
很多大型的计算机应用都需要处理大量的数据,这些数据通常不能一次性装入内存。但是访问存储在主存中的数据要比访问存储在磁盘或其他存储设备中的数据快得多, 所以对文件结构用于组织存储在磁盘中的大量记录时, 如何支持高效率的插入、删除和检索操作是非常重要的。一般来说, 有两种方法可以提高对磁盘中数据的操作: 一种是适当安排信息位置, 如果需要访问辅助存储器中的数据, 尽可能少的访问次数得到数据, 而且最好第一次访问就能得到; 另一种减少磁盘访问次数的方法是合理组织信息, 使每次磁盘访问都能得到更多的数据, 从而减少将来的访问需要。索引因此可以定义为将关键词值与该值对应的记录的磁盘位置联系起来的过程。索引的基本构件是索引项。一个索引项中有关键词值和指针,通过指针就可以找到含有此关键词值的记录,即一个索引项为:(关键词值,指针),多个索引项就构成了一个索引(表)。
索引本身也是一个文件,当索引很大时,也可以将其分块,建立高一层的索引,如此继续下去,直到最高级索引不超过一个块时为止,这样就得到了一个多级索引结构。索引通常置于磁盘或内存,内存中一般只存放最高级索引。一旦对一个大型数据文件建立了索引而形成了索引文件,则不论是对随机查找,还是对顺序查找都是方便的。
如何组织索引文件是索引技术中的主要问题,高效的组织方式必须便于数据的查找、更新和删除。线性索引将关键值进行排序,索引的时候通过如二分法等查找方法找到数据项,这种方法查找效率高,但是一旦插入或删除某个值,整个索引表都可能发生变化,因此这种方法只适用静态的数据库。而大多数数据库应用存在如下特性:
1. 存在大量的更新
2. 查找时可能使用一个至多个key值
3. 有范围的key值也可能用于查找。
树是数据结构中重要的非线性结构,由于其良好的动态性质得以在算法中大量应用。从存储上看,树的节点可以离散的存储,不必像数组那样必须有固定的大小,而是可以动态扩张;从操作上看,对树节点的插入/删除、查找、取后继等操作都具有良好的性能特性。因此树的数据结构是数据库索引的理想选择。
1. 二分查找树(BST)
二分查找树或者是一棵空树,或者是具有以下性质的二叉树:
(1) 若左子树不为空,则左子树上所有结点的值都小于它的根结点的值
(2) 若右子树不为空,则右子树上所有结点的值都大于或等于它的根结点的值
(3) 左子树跟右子树也分别为一棵二分查找树
查找特点键值时,从根节点出发,如果根节点与查找值相等,查找成功;否则,如果查找值小于根节点,则递归地查找左子树;如果查找值大于或等于根节点,则递归地查找右子树。若子树为空,查找不成功。查找算法的复杂度为logn。
在树中插入新节点时,首先执行查找算法,找出被插节点的父节点,判断被插节点是其父亲节点的左孩子还是右孩子,将被插节点作为叶子节点插入。被插节点都是叶子节点。
执行特定值的删除操作时,首先执行查找算法,找到该节点,如果节点是叶子节点,删除该节点并不影响树的结构,因此可以直接删除该节点。如果节点只有一棵子树(左子树或右子树),被删除节点的父节点成为该子树的父节点,并不影响整棵树的结构与性质。如果节点有两棵子树,要将该节点删除而不影响树的结构,有一个比较好的方法,就是在树里找到一个可以替换该节点的叶子节点(因为我们知道删除叶子节点并不影响树的结构),而为了保证替换后的树的性质不变,叶子节点必须是大于该节点的最小节点(右子树的最左节点),或小于该节点的最大节点(左子树的最右节点)(这样才能保证两棵子树,一边均小于该节点,一边均大于该节点)。如果树节点没有重复值,选择哪个值并没有什么区别,如果树节点是存在重复值的,那么我们必须选择来自右子树的大于被删除节点的最小值,因为右子树存放的是大于等于根节点的值,如果我们选择了左子树的最右节点,可能破坏树的性质。
二分查找树很容易引起树不平衡的问题,即一边子树比另外一边长很多,如果出现不平衡,则在检索时平均查找次数可能变大,使得查找效率大为降低,最极端的状况就是变成线性检索。即使通过插入控制使二分查找树相对平衡,如果树很庞大,也就是说,部分树节点在内存中,而部分树节点在磁盘上,如果节点很深,查找这个节点将经历多次读取磁盘的操作,这在很大程度上影响了检索的效率。因此,二分查找树更适于内查找,即所要查找的资料均放在内存中。
2. AVL树
要使BST能够在基于磁盘的索引中达到高效可用,必须解决两个问题:一是使树平衡;二是合理地安排节点在块中的组织方式,使得从根节点到叶节点所经历的磁盘块数尽量地少。AVL树正是为使BST平衡而提出来的。
AVL树可以看成是在二分查找树的基础上添加以下属性:对于所有节点,其左子树和右子树的高度最大为1。只要树的节点满足这个性质,对于存储了n个记录的AVL树,其高度最大为O(logn),这样,对一个值进行查找,路径最长为O(logn)。
AVL树的查找算法与BST自然是一样的,所以复杂度也为O(logn)。
为了维持AVL本身所特有的特性,AVL在插入与删除的操作上有所修改。首先考虑插入。在插入前,树本身符合AVL的性质(即左右子树高度最多只相关1),插入值后,左右子树的高度差最多为2,对于最底下的不平衡子节点S,存在四种可能的情况:
1. 额外的节点是S的左孩子的左孩子
2. 额外的节点是S的左孩子的右孩子
3. 额外的节点是S的右孩子的左孩子
4. 额外的节点是S的右孩子的右孩子
可以看到,1跟4是对称的,正如2跟3也是对称的一样。对于情况1跟4, 一个简单的旋转即可保持BST的性质。而对于情况2跟4, 则需要两次旋转,分别如下图所示:
至于删除,也是在BST的删除结果的基础上,考虑不平衡节点的旋转。因此,AVL的插入、删除操作跟BST的复杂度一样,均为O(logn)。它通过旋转规则,使树达到平衡,从而使树的高度降低,提高检索的效率。然而与BST一样的是,它更多的适用于内查找。对于基于磁盘的查找,同样没有比较好的组织方式。
3. 2-3树
2-3树不是一种二叉树,但他的形状满足以下性质:
(1) 一个节点包含一个或两个键值
(2) 每个内部节点有两个子节点(如果它有一个键值)或三个子节点(如果它有两个键值)
(3) 所有叶节点都在树结构的同一层,因此树的高度总是平衡的。
对于每个结点, 左子树中所有后继结点的值都小于第一个键的值, 而其中间子树中所有结点的值都大于或等于第一个键的值。如果结点有右子树的话( 相应地, 结点存储两个键值) , 那么其中间子树中所有后继结点的值都小于第二个键的值, 而其右子树中所有后继结点的值都大于或等于第二个键的值。同时,同一层的键值从左到右增大。
2-3树的查找方法与二分查找树相似,从根节点出发,如果在根节点找到查找值则查找成功返回,否则根据节点键的规则递归地查找下去,直到找到或返回失败。
在2-3树中插入新值时并不为其开辟一个新的叶子节点来存储,也就是说,2-3树不是向下生长的。插入算法首先找到一个合适的叶子节点来存放该值,使树的性质不被破坏。如果该叶子节点只包含一个值(每个节点都最多有两个值),则简单将该值放入叶子节点即可。如果叶子结点本身已经包含两个值了,则需要为前加入的叶子开辟新的空间。设节点L为插入节点,但是已经满了,也就是,这个节点因为包含了三个值,所以必须进行分裂,设新分裂出来的节点为L’,则L将存储这三个值中最小的那个值,而L’则存储这三个值中最大的那个。处于中间的值将得到提升,作为插入值晋升到父节点去。如果父节点只包含一个键值,该值直接放入节点即可,否则,同样的“分裂-晋升”过程将在该父节点进行,一直递归到根节点为止。
从2-3树删除一个节点,有三种可能情况需要考虑:最简单的情况是,如果删除的值存储在有两个键值的节点上,直接删除该值并不影响树的性质与结构。如果被删除的值所在的节点只有它一个键值,被删除后该节点将为空,因此通过向兄弟节点借一个记录,并修改父节点来解决。如果兄弟节点不够借,则需要合并相邻节点,并影响双亲,可能导致树的高度下降。如果被删除的值是树的内部节点,则将被删除记录用右边子树中的最小键值代替,然后再根据第一、二种情况将该值删除。
2-3树以比较小的代价维持了树的平衡,使树在相同记录的情况下尽量矮,从而提高了检索的速度。它同时也是后面的B-树使B+树的模型。
4. B-树
B树,或者B树的变种已经成为需要进行插入、删除、查找操作的应用的标准的文件组织形式,它解决了基于磁盘的查找树必须解决的主要问题,包括:
1. B树是一种平衡树,所有的叶子节点都在同一层上
2. 更新与查找操作只需动用几个磁盘块,所以性能比较好
3. B树把相关的键值放在同一个磁盘块上,很好地利用了近邻效果
4. B树保证所有的节点都有一个最低的饱合度,这样做的好处是提高了空间的效率同时又降低了获取磁盘的次数。
一棵阶数为m的B树必须满足以下的性质:
1. 根节点或者是叶节点,或者至少有两个孩子
2. 所有的内节点,除了根节点外,都必须有m/2到m个孩子
3. 所有的叶子节点都在同一层上,保证了树的平衡性
事实上,B树只是2-3树的一种泛化模式,2-3树是一种3阶的B树。一般的,一个B树节点为一个磁盘块的大小。查找、删除和插入操作跟2-3树也是一样的。
5. B+树
从理论上说,B 树可以广泛用于实现基于磁盘的大型系统, 但是却从来没有实现过。最普遍使用的是B 树的一个变体, 称为B+ 树。可以这样定义一棵B+ 树:
(1) 树中每个非叶子节点最多有m棵子树;
(2) 根结点至少有两棵子树,除根外,所有的非叶节点至少有m/2棵子树,有n棵子树的非叶节点有n-1个键值
(3) 所有的叶子节点处于同一层上,包含了全部键值及指向相应数据对象存放地址的指针,且叶节点本身按键值从小到大顺序连接
(4) 所有的非叶节点可以看作索引部分,节点中键值与指向子树的指针构成了对树的索引项。
B+树与B树的最显著的区别在于: B+树只在叶结点存储记录, 内部结点存储关键码值,但是这些关键码值只是用于引导索引检索位符,这意味着内部结点与叶结点在结构上有着显著的区别。内部节点存储关键码引导索引,每个关键码与一个指向儿子节点的指针相关联, 而叶结点存储实际记录。m阶B+树中的叶结点可能存储大于或者小于m个记录, B+树的叶节点通常链接起来以便于检索,这样可以看出B+树是B树的一种变形,它把叶子结点和其它结点区别开来,并且建立链路,可见其效率要优于2- 3 树和B 树。
发表评论
-
正则表达式的一些笔记
2012-08-16 23:30 01. 文字符号 1.1 特殊字符:[ ] \ ^ $ . | ... -
总共有多少个数独?
2012-05-12 15:31 12741憋屈地看了一个星期的 ... -
《算法引论》之算法分析
2012-04-26 14:01 1571上次写博客,已经是半个月之前了。我也不知道我这段日子在干嘛了, ... -
编程之美续
2012-04-06 15:37 1115看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也 ... -
编程之美
2012-04-02 16:54 1411前段日子又看了编程之美,后来闲着无聊学python去了,想着书 ... -
stl中的几个精美算法
2012-03-17 18:35 1161关于STL中的算法,我印象比较深刻的主要有用于list的sor ... -
STL和内存管理技术
2012-03-17 16:46 9717前段日子读了STL的源码 ... -
数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree)
2012-01-17 21:31 2761在《基于树的索引结构介绍》(http://philoscien ... -
编程珠玑--关于查找(二分法、自组织链、哈希)
2011-12-31 19:36 2103查找是我们现实生活中 ... -
编程珠玑 -- 关于堆
2011-12-28 15:31 1132堆是这样一种数据结构,它首先是一棵二叉树,而且还是一棵完全二叉 ... -
编程珠玑 -- 关于排序
2011-12-27 20:12 976《编程珠玑》主要提到 ... -
编程珠玑 -- 数据结构?
2011-12-21 21:15 658又开始看《编程珠玑》,发现之前看的也许不是很认真吧,再看一遍的 ... -
Moment in Peking
2011-06-05 17:01 1027"Moment in Peking" wa ... -
编程珠玑 -- swap section
2011-04-21 11:53 1164编程珠玑第二篇主要提出了三个思想: 1。 二分查找。(bin ... -
编程珠玑 -- bitSort
2011-04-21 11:05 953<C专家编程>看完了。 ... -
C专家编程--运行时数据结构
2011-04-13 15:26 995首先看一下编译完成后 ... -
C专家编程--指针与数组
2011-04-11 23:41 765指针与数组的根本区别 ... -
C专家编程--分析C语言的声明
2011-04-11 19:55 10351。 理解C语言声明的优先级规则 char* cpp; ... -
C专家编程--C语言中的符号重载
2011-04-10 17:48 888static 在函数内部,做为变量修饰符表示该变量的 ... -
C专家编程--C语言中的符号优先级
2011-04-10 17:47 865. 的优先级高于* *p.f ==> ...
相关推荐
3. B+树索引结构:B+树是一种广泛使用的树形结构数据索引方式,是B树的一种变种,特别适合用于磁盘存储。它能够有效地组织大量数据,并支持快速的查找、顺序访问、插入和删除操作。在数据库系统中,B+树被广泛用作...
在统一的框架下给出了各种数据空间网格划分的定义,讨论了两种适用于实现网格化数据索引的R树和PK树索引结构。试验结果表明,PK树在数据存储和索引上具有更高的效率,与网格化数据组织方法结合起来,对于降低...
总的来说,这个压缩包中的源代码提供了实现M树索引结构的完整框架,涵盖了从数据对象的存储到查询处理的各个层面。通过理解和修改这些代码,开发者可以深入理解M树的工作原理,并根据特定需求定制自己的多维索引解决...
1. **B树(B-Tree)**:B树是最常见的索引结构之一,适用于大型数据集。它的每个节点可以包含多个键和指向子节点的指针,这样就可以通过比较键值来快速找到目标数据。B树的高度决定了索引查找的效率,高度越低,查找...
实验结果表明,这种基于四元索引结构的优化方案在性能上比之前的五元索引结构有了显著的改善。 本文的研究成果,不仅对优化XPath查询具有重要的实际应用价值,也为数据库领域中处理XML数据提供了一种有效的解决路径...
为了有效地解决这一问题,本文提出了一种新的索引结构——基于有序二叉树的高效优化索引树(Optimized Trie Tree)。这种优化索引树不仅能够快速地完成字符串的检索工作,而且还能够显著减少所需的存储空间。 #### ...
4. **索引构建**:根据书籍信息构建B树索引,可能需要对信息进行编码以便于比较。 5. **查询优化**:设计高效的查询接口,提供按书名、作者等不同条件的检索功能。 6. **错误处理**:处理可能出现的异常情况,如...
本文所探讨的,是基于B+树的电力大数据分布式索引技术,这是一种结合了B+树索引结构和倒排索引的分布式混合索引结构。 首先,B+树是一种自平衡的树数据结构,它保持数据排序,并允许搜索、顺序访问、插入和删除操作...
1. **树结构**:如R树、R+树、R*树等,这些索引结构能够有效地组织多维数据,并支持高效的范围查询。 2. **线性映射**:例如,基于空间填充曲线(如Hilbert曲线、Z-order曲线等)的索引方法,能够保持空间邻近性的...
C语言数据结构课程设计基于B树为索引的图书管理系统源码。 基本要求] (1)每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。 (2)作为演示系统,不必使用文件,全部数据可以都在内存存放。...
在图书管理系统中,B树作为索引结构,可以快速定位图书信息,提高查询效率。 在图书管理系统的实现中,我们需要定义以下几个核心功能: 1. **节点结构**:设计B树的节点,包括键值、指针以及指向子节点的指针数组...
其中,B树索引是一种广泛应用于关系型数据库中的数据结构。B树(Balance Tree)是一种自平衡的树结构,能够保持数据有序,并且在插入、删除等操作时自动调整结构以维持平衡,因此非常适合用来实现索引。 B*树(B-...
以下将详细介绍在LabVIEW中如何使用和操作树形结构,并基于提供的文件名进行解析。 1. **树形结构基础** 树形结构在LabVIEW中通常以"Tree Control"的形式出现,它是一个用户界面组件,可以展示多级节点,每个节点...