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