- 浏览: 165474 次
- 性别:
- 来自: 广州
博客专栏
-
TCP/IP详解卷一>阅读...
浏览量:12264
文章分类
最新评论
-
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 12649憋屈地看了一个星期的 ... -
《算法引论》之算法分析
2012-04-26 14:01 1524上次写博客,已经是半个月之前了。我也不知道我这段日子在干嘛了, ... -
编程之美续
2012-04-06 15:37 1030看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也 ... -
编程之美
2012-04-02 16:54 1360前段日子又看了编程之美,后来闲着无聊学python去了,想着书 ... -
stl中的几个精美算法
2012-03-17 18:35 1119关于STL中的算法,我印象比较深刻的主要有用于list的sor ... -
STL和内存管理技术
2012-03-17 16:46 9598前段日子读了STL的源码 ... -
数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree)
2012-01-17 21:31 2705在《基于树的索引结构介绍》(http://philoscien ... -
编程珠玑--关于查找(二分法、自组织链、哈希)
2011-12-31 19:36 2032查找是我们现实生活中 ... -
编程珠玑 -- 关于堆
2011-12-28 15:31 1097堆是这样一种数据结构,它首先是一棵二叉树,而且还是一棵完全二叉 ... -
编程珠玑 -- 关于排序
2011-12-27 20:12 897《编程珠玑》主要提到 ... -
编程珠玑 -- 数据结构?
2011-12-21 21:15 624又开始看《编程珠玑》,发现之前看的也许不是很认真吧,再看一遍的 ... -
Moment in Peking
2011-06-05 17:01 989"Moment in Peking" wa ... -
编程珠玑 -- swap section
2011-04-21 11:53 1116编程珠玑第二篇主要提出了三个思想: 1。 二分查找。(bin ... -
编程珠玑 -- bitSort
2011-04-21 11:05 900<C专家编程>看完了。 ... -
C专家编程--运行时数据结构
2011-04-13 15:26 963首先看一下编译完成后 ... -
C专家编程--指针与数组
2011-04-11 23:41 717指针与数组的根本区别 ... -
C专家编程--分析C语言的声明
2011-04-11 19:55 9871。 理解C语言声明的优先级规则 char* cpp; ... -
C专家编程--C语言中的符号重载
2011-04-10 17:48 810static 在函数内部,做为变量修饰符表示该变量的 ... -
C专家编程--C语言中的符号优先级
2011-04-10 17:47 789. 的优先级高于* *p.f ==> ...
相关推荐
#资源达人分享计划#
针对R-树索引空间查询效率低下的问题,提出一种基于节点分裂优化的R-树索引结构:SR-树索引。SR-树索引在节点分裂过程中,通过增加叶子节点的空间数据聚集性来减少叶子节点最小外接矩形的覆盖面积。为了有效降低磁盘...
在统一的框架下给出了各种数据空间网格划分的定义,讨论了两种适用于实现网格化数据索引的R树和PK树索引结构。试验结果表明,PK树在数据存储和索引上具有更高的效率,与网格化数据组织方法结合起来,对于降低...
该文给出了一个XML树数据模型的形式化定义.将编码方案、逆序列表和路径索引的思想相结合,提出 ...实验结果表明,该文给出的基于XML索引结构实现双亲/孩子关系和拥有关系的结构连 接算法是高效的、健壮的.
数据结构课程设计:基于B树为索引的图书管理系统.zip
基于混合聚类的静态空间数据索引分析,靳雅,杨永国,R树索引结构是目前公认的针对空间数据的索引结构,它适合动态索引,而专用于静态空间数据环境下的索引结构较少。静态空间数据组�
将Huffman树型结构及其编码的思想引入密文索引结构的构建方案中,改进基于知识理解的中文分词算法提取明文关键词,通过改进的TF-IDF规则对检索结果集进行排序以返回最符合用户需求的Top-k个结果,并增加伪造的索引...
针对MapReduce数据块处理机制、高维数据分布特征和KNN查询需求,设计一种基于B 树的高维索引结构(iPartition),创新性提出基于主成分区分度的优化数据划分策略和邻接数据域分散存储等原则,将数据均匀划分到不同的...
C语言数据结构课程设计基于B树为索引的图书管理系统源码。 基本要求] (1)每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。 (2)作为演示系统,不必使用文件,全部数据可以都在内存存放。...
区块链上基于B+树索引结构的密文排序搜索方案
针对三维结构模型中地质体层状分布、厚度较小、形状极不...数据测试表明,基于STR算法的多体R树索引整体性能优于传统R树,并且多体索引构建预处理中X、Y、Z的选取顺序对不同类型地质结构模型的查询性能也有不同影响。
索引树及基于索引树的二叉堆,何颖,,本文提出一种性质介于树 与数组之间的数据结构—索引树。索引树在数据量无限制的增加但又需要对数据随机访问的情形下具有良好的��
C语言数据结构基于B树为索引的图书管理系统源码+课程设计报告,对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统,将上述业务活动借助于计算机系统完成
针对DSPdigital signal processor, 数字信号处理器平台上的图像特征点匹配问题, 提出了一种高效的基于自聚类二分查找树的快速索引结构, 并设计了适合于DSP结构特点的索引存储布局。通过在离线情况下将特征点参考数据...
并通过对海量数据非主键索引结构的研究, 结合统一存取的描述理念, 提出了基于HDFS的一种可适用于B-树和R-树及其变种的层次索引结构, 改变了原键—值存储在非主键索引结构中的劣势。通过提出Hadoop缓冲策略、基于随机...
MySQL的MyISAM、InnoDB引擎默认均使用B+树索引(查询时都显示为“BTREE”),本文讨论两个问题:为什么MySQL等主流数据库选择B+树的索引结构?如何基于索引结构,理解常见的MySQL索引优化思路?索引结构的选择基于...
基于改进四叉树索引的矢量地图叠加分析算法 描述了改进的空间叠加分析方法 是学习图形学算法和数据结构的很资料 特别是对于GIS开发的人员来特别有用
综合分析了R-树和四叉树在处理移动对象的连续K近邻(简称CKNN)查询算法中的不足,提出了一种基于R树和四叉树索引结构,去解决移动对象连续K近邻查询算法。该算法通过对移动对象分配静态空间,并在研究区域内利用QR-...
4. 提出一种基于 GPU 缓存敏感 CSB+-树索引的无锁并行处理方案,该方案通过对传统的 CSB+-树的结构改进,可实现 CSB+-树的索引数据在 GPU 上动态更新。在 GPU上提出基于树层和基于节点索引键 CSB+-树两种并行构建...