数据库的存储结构文件记录的组织和索引技术.docx
《数据库的存储结构文件记录的组织和索引技术.docx》由会员分享，可在线阅读，更多相关《数据库的存储结构文件记录的组织和索引技术.docx（17页珍藏版）》请在冰点文库上搜索。
数据库的存储结构文件记录的组织和索引技术
数据库的存储结构（文件、记录的组织和索引技术）
by沈燕然0124141
利用课余时间自学了第6章《数据库存储结构》，对于数据库不同层次的存储结构，文件记录组织和索引技术有了一定的了解，在这篇札记中将会结合一些具体应用中涉及到的数据存储和索引知识，以及通过与过去学习过的一些数据结构比较来记录自己学习的心得体会。
这些实例涉及不同的数据库系统，如Oracle,DB2和Mysql等等，它们之间会有一些差异。
不过本文旨在探讨数据存储方面的问题，因而兼容并包地将其一并收入，凡是可能需要说明之处都会加上相应的注解。
：
）
1、数据库（DBS）由什么组成？
——逻辑、物理和性能特征
1、什么是数据库系统（DBS）——DBS用文件系统实现
在关系模型中，我们把DBS看成关系的汇集。
DBS存在的目的就是为了使用户能够简单、方便、容易地存取数据库中的数据。
因此在用户的眼中，数据库也就是以某种方式相关的表的集合。
用户并不需要去关心表之间关系，更不需要了解这些表是怎样存储的。
但是我们现在从DBA（数据库管理员）的角度来看，情况就比那稍稍复杂一点。
实际的数据库包含许多下面列出的物理和逻辑对象：
∙表、视图、索引和模式（确定数据如何组织）
∙锁、触发器、存储过程和包（引用数据库的物理实现）
∙缓冲池、日志文件和表空间（仅处理如何管理数据库性能）
2、什么是表空间？
——表空间相当于文件系统中的文件夹。
表空间被用作数据库和包含实际表数据的容器对象之间的一层，表空间可以包含多个不同的表。
用户处理的实际数据位于表中，他们并不知道数据的物理表示，这种情况有时被称为数据的物理无关性。
oracle数据库表空间的实例图
上图描述了一个ORACLE数据库大致的表空间组织，USER中存放主要的数据表,TEMP存放临时数据表,INDX存放索引,TOOLS存放回退段（RBS）.
表空间在DB2数据库系统中是比较典型的说法，在Mysql等系统中也直接使用文件系统中文件夹的概念。
新建一个表的时候可以指定它所在的表空间，至于用文件具体存储数据时如何存储这可能就是各个数据库系统的商业机密了，至少DB2是这样。
另外值得关注的一点是不同于oracles对表空间的严格要求，Mysql的数据库形式相对比较简单，以文件夹的形式存放在安装目录的/data/下面，该数据库的每一个表对应两个文件，一个存放表中数据，另一个存放元数据信息，也就是建表时指明的列属性等等信息。
3、文件中的记录在物理上如何实现？
——文件组织形式
在外存中，DB以文件形式组织，而文件由记录组成。
文件结构由OS的文件系统提供和管理。
文件组织有两种方式——定长记录格式和变长记录格式。
那种格式更好？
定长记录格式——优点是插入操作较简单。
缺点是对记录长度有硬性要求，而且有的记录可能横跨多个快，降低读写效率。
变长记录格式——优点是记录长度自由方便
缺点是记录长度差异导致删除后产生大量“碎片”，记录很难伸长，尤其“被拴记录”移动代价相当大。
中庸之道——预留空间和指针方式
记录长度大多相近——采用预留空间方法，取最大记录长为统一标准，在短记录多于空间处填特定空值或记录尾标志符。
记录长度相差很大——采用指针形式（每纪录后的指针字段把相同属性值记录链接起来）。
文件中使用两种块——固定块（存放每条链中第一条记录）和溢出块（存放其余纪录）。
3、记录在文件中怎样组织？
堆文件组织
记录可以放在文件的任何位置上，一般按输入顺序放置。
记录的存储顺序与关键码没有直接的联系。
删除操作只加删除标志，新插入记录总在文件尾。
顺序文件组织
如图所示，在这种组织中记录按查找键值升序或降序的顺序存储。
散列文件组织
据记录的某个属性值通过散列函数求得得知作为记录的存储地址（即“块号”）。
这个技术通常与索引技术连用。
什么是散列表中的冲突？
（也称桶溢出）
一个重要的考虑因素是采用散列表组织是有可能会发生冲突。
（1）概念
两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。
该现象称为冲突（Collision）或碰撞。
发生冲突的两个关键字称为该散列函数的同义词（Synonym）。
【例】上图中的k2≠k5，但h（k2）=h（k5），故k2和K5所在的结点的存储地址相同。
（2）安全避免冲突的条件
①其一是|U|≤m
②其二是选择合适的散列函数。
这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。
（3）冲突不可能完全避免
通常情况下，h是一个压缩映像。
虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。
因此，只能在设计h时尽可能使冲突最少。
同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。
（4）影响冲突的因素
冲突的频繁程度除了与h相关外，还与表的填满程度相关。
设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子（LoadFactor）。
α越大，表越满，冲突的机会也越大。
通常取α≤1。
聚类文件组织
主要特点——一个文件存储多个关系的记录。
不同关系有联系的记录存储在同一块内可以提高查找速度和I/O速度。
由这种组织的特性可以看出，它适用于大容量数据库中，可以用来提高查询效率。
聚类文件管理由DBS实现，而前三种组织中文件的管理由OS来实现。
4、索引技术
为什么要索引？
实例分析1：
Mysql索引分析
假设我们创建了一个名为people的表：
CREATETABLEpeople（peopleidSMALLINTNOTNULL,nameCHAR（50）NOTNULL）;
然后，我们完全随机把1000个不同name值插入到people表。
可以看到，在数据文件中name列没有任何明确的次序。
如果我们创建了name列的索引，MySQL将在索引中排序name列：
对于索引中的每一项，MySQL在内部为它保存一个数据文件中实际记录所在位置的“指针”。
因此，如果我们要查找name等于“Mike”记录的peopleid（SQL命令为“SELECTpeopleidFROMpeopleWHEREname='Mike';”），MySQL能够在name的索引中查找“Mike”值，然后直接转到数据文件中相应的行，准确地返回该行的peopleid（999）。
在这个过程中，MySQL只需处理一个行就可以返回结果。
如果没有“name”列的索引，MySQL要扫描数据文件中的所有记录，即1000个记录！
显然，需要MySQL处理的记录数量越少，则它完成任务的速度就越快。
——由此可见，索引可以大大提高DBS处理数据的速度！
索引分类
有序索引（orderedindices）：
根据记录中牟中排序顺序建立的索引。
散列索引（hashindices）：
根据记录中某个属性值，通过散列函数得到的函数，作为存储空间的桶号。
实例分析2：
ORACLE数据库性能优化方案
Row-resequencing（行的重新排序）
就象我们上面提到的，有经验的OracleDBA都知道I/O是响应时间的最大组成部分。
其中磁盘I/O特别厉害，因为当Oracle由磁盘上的一个数据文件得到一个数据块时，读的进程就必须等待物理I/O操作完成。
磁盘操作要比数据缓冲慢10,000倍。
因此，如果可以令I/O最小化，或者减少由于磁盘上的文件竞争而带来的瓶颈，就可以大大地改善Oracle数据库的性能。
如果系统响应很慢，通过减少磁盘I/O就可以有一个很快的改善。
如果在一个事务中通过按一定的范围搜索primary-key索引来访问表，那么重新以CTAS的方法组织表将是你减少I/O的首要策略。
通过在物理上将行排序为和primary-key索引一样的顺序，就可以加快获得数据的速度。
就象磁盘的负载平衡一样，行的重新排序也是很简单的，而且也很快。
通过与其它的DBA管理技巧一起使用，就可以在高I/O的系统中大大地减少响应的时间。
在高容量的在线事务处理环境中（onlinetransactionprocessing，OLTP），数据是由一个primary索引得到的，重新排序表格的行就可以令连续块的顺序和它们的primary索引一样，这样就可以在索引驱动的表格查询中，减少物理I/O并且改善响应时间。
这个技巧仅在应用选择多行的时候有用，或者在使用索引范围搜索和应用发出多个查询来得到连续的key时有效。
对于随机的唯一primary-key（主键）的访问将不会由行重新排序中得到好处。
让我们看一下它是如何工作的。
考虑以下的一个SQL的查询，它使用一个索引来得到100行：
Selectsalary
fromemployee
wherelastnamelike‘B%’
这个查询将会使用last_name_index，搜索其中的每一行来得到目标行。
这个查询将会至少使用100次物理磁盘的读取，因为employee的行存放在不同的数据块中。
不过，如果表中的行已经重新排序为和last_name_index的一样，同样的查询又会怎样处理呢？
我们可以看到这个查询只需要三次的磁盘I/O就读完全部100个员工的资料（一次用作索引的读取，两次用作数据块的读取），减少了97次的块读取。
重新排序带来的性能改善的程度在于在你开始的时候行的乱序性如何，以及你需要由序列中访问多少行。
至于一个表中的行与索引的排序键的匹配程度，可以查看数据字典中的dba_indexes和dba_tables视图得到。
在dba_indexes的视图中，查看clustering_factor列。
如果clustering_factor的值和表中的块数目大致一样，那么你的表和索引的顺序是一样的。
不过，如果clustering_factor的值接近表中的行数目，那就表明表格中的行和索引的顺序是不一样的。
行重新排序的作用是不可以小看的。
在需要进行大范围的索引搜索的大表中，行重新排序可以令查询的性能提高三倍。
有序索引的分类：
索引文件由两个成份组成。
索引和主文件。
对主文件可以建立几套不同的索引。
如果索引的查找键值顺序与主文件一致，则称这种索引为主索引（聚类索引），如果不一致，则称这种索引为辅助索引（非聚类索引）。
主索引的实现
快捷但昂贵——稠密索引（denseindex）我们可以看到每一个查找键值（在图中即为学生姓名）都建立了一个索引记录，包括查找键值和指向该值的记录链表中第一个记录指针。
之所以昂贵是因为需要维护所有指针，但也正是因为指针多才使得查找方便而快捷。
节约但低效——稀疏索引（sparseindex）若干查找键值（姓名）才建立一个索引记录。
减少指针使空间耗费降低，但同时也降低了查找效率。
有没有折衷的方案？
当然我们也可以把两种方法综合起来，对数据建立denseindex之后，在多少有些庞大的index之上再建立一个sparseindex，从而使得查询的速度得到提高。
其实这已经透露出了某种多极索引的信息了，接下来就要设计者一方面的内容。
如果数据量很大怎么办？
在01级同学中查找未勒同学的选课纪录尚且容易，因为仅01级的学生选课记录数不大，如果是在复旦大学所有学生的学科记录中搜索未勒同学的选课记录呢？
我们可以里料想到，随着数据量的急剧膨胀，无论是顺序查找还是索引查找，数据库的性能都会恶化。
虽然可以通过重组文件（改变文件的记录排序，正如前面看到的对oracle数据库所作的性能优化一样）来改善，但是频繁的重组增加了系统的负担。
因此我们引进多级索引的概念
索引很大时建立索引的索引（多级索引），因为外层索引块可常驻内存，因而找记录室内层索引块读一次就行。
具体实现时可把每一级索引与一个物理存储单位联系起来,方便实现。
一个多级索引的例子
流行的技术——平衡树技术
定义——m阶平衡树或者为空，或者满足以下条件：
每个结点至多有m棵子树；
根节点或为叶结点，或至少有两棵子树
每个非叶结点至少有
棵子树
从根节点到叶结点的每一条路经都有同样的长度，即叶结点在同一层次上。
主流应用——B+树技术
B+树的结构（插图）
叶结点——每个节点中至多有m-1个,至少有ceiling[（m-1）/2]个searchkeyK1,K2,……，Km-1,且searchkeyvalue不允许重复.至多有m个指针P1,P2,……，Pm,指针指向主文件中的记录。
譬如Pi指向查找键值为Ki的主记录.如果B+树索引是denseindex,则每个searchkey必须在某个叶结点中出现
查找键为primarykey->指针指向记录
查找键非primarykey->指针指向存放具有searchkey值主记录指针的桶
*每个叶结点中至少应有searchkey,至多有m-1个searchkey,.
非叶结点——每个结点（不包括根节点）中至少有
个，至多有m个指针，指针数称为“扇出系数”（fanout）。
指针Pi指向的子树中所有searchkey满足Ki-1<=searchkeyvalue只有根节点中searchkey数可以小于
，其他结点查找键数目至少应为ceiling[（m-1）/2]。
B+树和二叉树的比较
B+树结构与内存中普遍使用的二叉排序树的主要区别是结点的大小以及树的高度。
在二叉排序树中，每个结点很小，只有一个键值和两个指针，而B+树中每个结点很大，可以是磁盘上的一个块，包含很多查找键值和指针。
二叉排序树显得瘦而高，而B+树则显得矮而胖。
在平衡的二叉排序树中，如果查找键的值有100万个，那么查找的结点数约为log2（k）=20；如果文件采用二叉排序树方法，就要读20个物理块.而在同样情况下,B+树索引只要读4块即可.所以在外存中普遍使用B+树结构,而不用二叉排序树结构.
二叉排序树结构示意图B+树示意图
B+树和B树的比较
B树索引类似B+树索引，主要区别在于B树中所有查找键值只出现一次。
在B+树中，每个查找键值都必须在叶结点中出现，为了组织多级索引，某些查找键值还必须在上层节点中出现。
而对B树来说查找键值可以出现在任何节点上，但只能出现一次。
显然，B树中的查找键值数目比B+树少。
B+树的性能参数
阶数m——如果提高B_树的阶数m，可以减少树的高度，从而减少读入结点的次数，因而可减少读磁盘的次数。
事实上，m受到内存可使用空间的限制。
当m很大超出内存工作区容量时，结点不能一次读入到内存，增加了读盘次数，也增加了结点内搜索的难度。
高度h——需要读写磁盘的次数=找插入结点向下读盘次数+分裂非根结点时写盘次数+分裂根结点时写盘次数=h+2（h-1）+3=3h+1。
B+树的特点
B+树索引的突出特点是很好地解决了键值的插入、溢出、删除和空间回收等问题，从而使B+树索引可以适应成批插入、文件易变的情况；B+树索引在操作中可“动态地”进行维护，无须周期性地重新组织文件；还可以采用压缩索引项的办法，提高扇出率，降低树的高度，减少读取次数，加快查找速度。
因此B+树索引是组织大型索引文件的一种最主要的方法。
B+树索引实现了索引键值的唯一化，即一个键值在B+树索引中只有一个唯一的入口.
5、散列技术散列和可扩充散列
名词解释——桶（bucket）-〉即页块，也就是操作系统一次内外存交换可以读些的存储空间，例如1024个字节。
我们能做得更好吗?
散列函数是一种不必通过索引就能访问数据的方法,在散列技术基础上结合索引方法可进一步提高访问效率.使用散列函数能使我们提高数据表查询的效率。
怎样构造一个行之有效的散列函数？
构造散列函数有几个基本的原则：
1．散列函数的定义域必须包括需要存储的全部关键码。
如果散列表允许有m个地址，其值域必须在0到m-1之间；
2．散列函数计算出来的地址应能均匀分布在整个地址空间中，对于从关键码集合中随机抽取的关键码散列函数应能以同等概率取到每一个可能值。
3．散列函数应该尽量简单，能在较短时间内计算出结果。
先来看一个例子，假设我们现在要把一组关键码存储在数据库里面，这组关键码为{942148，941269，940527，941630，941805，941558，942047，940001}
几种常见的散列函数:
1.直接定址法
说明：
Hash（key）=a*key+b（a,b为常数）
应用：
Hash（942148）=2148Hash（941269）=1269Hash（940527）=527
Hash（941630）=1630Hash（941805）=1805Hash（941558）=1558
Hash（942047）=2047Hash（940001）=1
2.数字分析法
说明：
先把关键码各位编号，再去其中有代表性的几位结合散列表地址范围作为函数值。
应用：
942148
941269
940527
941630
941805
941558
942047
940001
（1）
（2）（3）（4）（5）（6）
3.除留余数法
Hash（key）=key%pp<=m
4.乘余取整法
Hash（key）=|_n*（A*key%1）_|
“A*key%1”表示取A*key的小数部分
值得一提的是Knuth对常数A的取法做过仔细的研究，最佳的选择与代散列的数据特征有关。
一般取A=0.618左右效果比较理想。
5.平方取中法
此方法在词典处理中使用十分广泛，现计算构成关键码的标志符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。
6.折叠法
此方法把关键码从左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
然后把这些部分的数据迭加起来就得到地址。
前面在学习散列文件组织的时候我们已经提到了三列组织中关于桶溢出的处理,也就是散列组织中的冲突,这里为了完整性再给出一个实例：
实例分析3：
有一组表项，其关键码分别是
12361,07251,03309,30976
采用的散列函数是
hash（x）=x%73+13420
其中，“%”是除法取余操作
则有：
hash（12361）=hash（07250）=hash（03309）=hash（30976）=13444。
就是说，对不同的关键码，通过散列函数的计算，得到了同一散列地址。
我们称这些产生冲突的散列地址相同的不同关键码为同义词
下面着重分析散列冲突（桶溢出）的处理方法.
1.封闭散列法——溢出桶拉链法
这种方法和生活中解决桶里的水溢出的方法有些类似，如果某个桶（称为基本桶）已经装满而还有新的记录要装入（还要往桶里倒水），那么就由系统提供一个溢出桶用指针链接在基本桶的后面来容纳那些多出来的水（也就是多余的记录）。
记录的查找不仅要在基本桶中完成，也可能要到后面链接的溢出桶中进行。
2.开放散列法
这种方法同样也很容易理解，还是看桶接水的例子。
这次如果基本桶不够用了，我们就再从可以用的基本桶里面找一个空的来接水，而不是把专用的溢出桶接在基本桶的后面。
不过在这里桶的选择挺有讲究的，分为线性探查法和再散列探查法。
所谓线性探查法就是我们在使用过的桶之后顺序选择一个有空闲空间的桶，把新纪录装进去；而再散列探查法则体现了递归的思想，顾名思义，我们再次使用散列方法来跳跃地选择一个空桶来装入新纪录。
注意到所谓空的桶并非一点水都没有，而是尚有容纳新记录的空间，标志散列组织装满程度的因子a称为“装填因子”或“负载因子”。
A等于存储纪录的空间量与给定的存储空间量的商。
一般a取0.6到0.8，如果a太大，大于0.8则容易发生桶溢出，同样如果a太小，小于0.6的话则浪费的空间太多。
开散列法和闭散列法的性能比较
散列可以用来提高索引效率吗?
“散列索引”就是把searchkeyvalue和指针一起组合成散列文件结构的一种索引.散列索引的构造方法如下:
首先为主文件中每个searchkeyvalue建立一个索引记录,然后把这些索引记录组织成散列结构（称为”散列索引”）,而不是denseindex或sparseindex.
概念说明——散列索引是一种辅助索引结构，不属于主索引结构，但是因为散列文件组织提供由索引直接找主记录的方法，所以我们也可以认为散列文件组织提供了一个虚拟的主散列索引。
我需要更多的桶，怎么办？
前面提到的都是静态索引，也就是说一旦散列函数确定了，桶和桶空间都不能更改了。
但是在实际应用中很有可能会出现这样的情况——数据库里的数据以惊人的速度大量增长，我们会发现这些桶已经不够用了，那怎么办呢？
采取可扩充散列结构可以解决这个问题。
可扩充散列结构实际上是对静态散列结构中“成倍扩充法”的改进，因为有动态处理的能力，因此能够从容的应付数据库经常性的增长和收缩。
空间利用率高，每次重新组织只是一个桶的增加或者减少。
首先我们要选择一个均匀性和随机性都比较好的散列函数h,并使它产生一个较大的，由b个二进制位构成的整数。
每个散列值并不立即对应一个桶空间，而是根据实际需要申请或释放。
初始时我们根据这b位的前i位（高位）得出桶地址值，之后随数据增长取的位数i也随之增加。
这i位组成的值机为桶号，存放在“通地址表”中，指明桶的位置。
B树和可扩充散列——哪种方法更好？
我们已经了解了好几种散列方法，那么哪种通常情况下是最优的呢？
我们需要对性能进行分析，在时间与空间上进行权衡。
用基于目录的可扩充散列方法进行检索，仅需要2次磁盘访问。
采用这种方法的优点是不存在溢出问题，所以访问时间与文件大小无关，时间开销达到O
（1），其性能非常好。
但增加不均匀分布的关键码可能会导致目录扩充一倍，许多指针指到同一个桶会消耗许多存储空间。
可扩充散列的桶空间利用率在0.53到0.94之间周期性的变动。
如果与B树和B+树相比，B树和B+树的桶空间利用率在67%左右，但在插入时由于重新分布关键码，它们的空间利用率可以达到85%。
所以可扩充散列的存储利用率逊色于B树和B+树，但是在搜索的时间开销方面又优于它们，属于用空间换取时间的策略。
为什么有“周期性变动”？
因为我们的关键码具有随机分布的地址，可扩充散列表的桶在同样的时间间隔内逐渐充满，因此以同样的时间间隔分裂。
当桶充满到90%以上时就开始进行桶分裂，桶的空间利用率就会降低到50%，这就导致桶的存储利用率周期性变动。
我要查多个属性，可不可以增加查找键？
5、多键访问
当我们需要在数据库里查询同时符合几项条件的记录时，如果每次都应用单键查询，这样写出来的sql语句就会相当长而且有着极为繁琐的嵌套结构，更要命的是在数据库按照这样的单键查询进行操作的时候事实上每一次单键查询都会生成庞大冗杂的中间表，从而大大降低了效率也减慢了数据操作的速度。
因此我们就想到了能否同时对几个属性值进行查询，幸运的是这样的做法是行得通的，这就是多键查询的方法。
在多键查询中，我们可以把多于一个的属性值一起作为一个查找键，建立一个索引，这种索引与前面提到的索引技术本质上没有什么区别，除了属性值多了一点之外。
查找键之间的比较是按照字典顺序来进行的。
但是因为多键访问的查询语句应用的是比较操作而非等值操作，前面的索引技术不再适用，我们
升级会员 