数据存储结构二

1、An Introduction to Database System数据库系统概论数据库系统概论An Introduction to Database System数据库存储结构数据库存储结构B+树索引的结构树索引的结构 v B+树索引的结构满足： B+树索引是一个多级索引，但其结构不同于多级顺序索引。 B+树索引采用平衡树结构，即每个叶结点到根的路径长度相同。江宏江宏李勇李勇彭好彭好王红王红刘强刘强黄黄红红黄黄勇勇江宏江宏 李冰李冰 李立李立李勇李勇刘欢刘欢指向文件记指向文件记录录刘强刘强 孟晨孟晨 聂东聂东彭彭好好邱邱南南王王红红张张可可赵赵雪雪指向文件记录指向文件记录B+树索引的结构树索

2、引的结构 v B+树索引的结构满足： B+树索引是一个多级索引，但其结构不同于多级顺序索引。 B+树索引采用平衡树结构，即每个叶结点到根的路径长度相同。 B+树索引中的所有结点的结构都相同，它最多包含n-1个搜索码值K1, K2, , Kn-1，以及n个指针P1, P2, , Pn，每个结点中的搜索码值升序存放，即如果ij，那么KiKj。典型的B+树索引中的结点结构如图7-15所示。 每个非叶结点有 n/2 到n个孩子结点，n对特定的树是固定的。B+树索引的结构树索引的结构 v 叶结点的结构：对i=1, 2, , n-1，指针Pi指向具有搜索码值Ki的一条文件记录或指向一个指针桶，且指针桶中的

3、每个指针指向具有搜索码值Ki的一条文件记录。桶结构只在搜索码不是候选码且文件记录不按搜索码顺序存放时才使用。指针Pn有特殊的作用，稍后再讨论。江宏江宏李勇李勇彭好彭好王红王红刘强刘强黄红黄红黄勇黄勇江宏江宏李冰李冰李立李立李勇李勇刘欢刘欢指 向 文 件 记指 向 文 件 记录录刘强刘强 孟晨孟晨 聂东聂东彭好彭好邱南邱南王红王红 张可张可赵雪赵雪指向文件记录指向文件记录v每个叶结点最多可存放n-1个搜索码值，最少也要存放 (n-1)/2 个搜索码值。各个叶结点中的搜索码值不重复且不相交，并要使B+树索引成为稠密索引，即数据文件中的所有互不相同的搜索码值必须在某个叶结点出现且只出现一次。v每个叶

4、结点中的搜索码值升序排列，所以可以利用各个叶结点的指针Pn将所有叶结点按搜索码值的排序顺序链接在一起。这种叶结点的链接排序能够高效地实现对数据文件的顺序处理，而B+树索引中的其他结构能够高效地实现对数据文件的随机处理。如图7-16所示。 B+树索引的结构树索引的结构 v非叶结点的结构： B+树索引中的非叶结点形成叶结点上的一个多级(稀疏)索引。 非叶结点的结构与叶结点相同，只不过非叶结点中的所有指针都是指向B+树中下一层结点的指针。 每个非叶结点最多可存放n个指针(对应于存放n-1个搜索码)，最少也要存放 n/2 个指针(对应于存放 (n-1)/2 个搜索码)。 一个结点中存放的指针数称为该结

5、点的扇出。B+树索引的结构树索引的结构 v假设一个非叶结点中存放了m个指针， n/2 mn。 若mnr/fr，否则肯定会发生桶溢出。其中nr表示将要存储的记录总数，fr表示一个桶中能存放的记录数目。当然，这是以在选择散列函数时记录总数已知为前提的。 偏斜。某些桶分配到的记录比其他桶多，所以，即使其他桶仍有空间，有些桶仍可能溢出，称为桶偏斜。 偏斜发生的原因有两个： 多个记录可能具有相同的搜索码值； 所选择的散列函数可能会造成搜索码值的分布不均匀。桶溢出的处理桶溢出的处理v 桶溢出的处理方法：主要有闭散列和开散列二种方法。 闭散列： 如果一条记录必须插入桶b中，而桶b已满，系统会为桶b提供一个溢

6、出桶，并将此记录插入到这个溢出桶中。 如果溢出桶也满了，系统会再提供一个溢出桶，如此继续下去。 一个给定桶的所有溢出桶用一个链接列表链接在一起，如图所示. 使用这种链接列表的溢出处理称为溢出链。溢出链的散列结构称为闭散列。 桶溢出的处理桶溢出的处理 开散列： 它的桶的数量是固定的，没有溢出链； 当一个桶满了以后，系统将记录插入到初始桶集合B的其他桶中去。 选择其他桶的策略有： 使用下一个(按轮转顺序)未满的桶，该策略称为线性探查法； 用进一步计算散列函数的方法（再散列法）。 散列索引散列索引 v散列索引(hash index)将搜索码值及其相应的文件记录指针组织成散列文件结构。v散列索引的构建

7、方法： 将散列函数作用于一条文件记录的搜索码值，以确定索引项的散列桶； 将由该搜索码值以及相应文件记录指针组成的索引项存入散列桶(或溢出桶)中。v图7-22所示的是Student文件的一个辅助散列索引，其搜索码是studentNo，散列函数是计算studentNo值的各位数字之和后按5取模。由于studentNo是主码，所以每个搜索码值只对应一个记录指针。一般情况下，每个搜索码值可能对应多个指针。散列索引散列索引散列索引散列索引v散列索引只能是一种辅助索引结构。 散列索引从来不需要作为主索引(聚集索引)来使用，因为一个文件如果自身是按散列组织的，就不必再在其上另外建立一个独立的散列索引了。 不

8、过，既然散列文件组织能像索引那样提供对记录的直接访问，不妨就认为以散列形式组织的文件上也有一个聚集散列索引了。 动态散列动态散列 v 前面介绍的散列技术称为静态散列，它要求在选择散列函数时就知道记录的总数，即桶的数量必须事先确定。v 然而，大多数数据库都会随时间而变大。对于规模变化的数据库使用静态散列，有3种选择： 根据当前文件大小选择散列函数。这种选择会使性能随数据库增大而下降。 根据预计的将来某个时刻文件的大小选择散列函数。尽管这样可以一定程度上避免性能下降，但初始时会造成相当大的空间浪费。 随着文件增大，周期性地对散列结构进行重组。重组是一个复杂、耗时的操作，而且重组期间必须禁止对文件的

9、访问。v 动态散列技术允许散列函数动态改变，以适应数据库增大或缩小的需要。v 限于篇幅，这里不对动态散列技术进行讨论，有兴趣的读者请参考相关资料。散列与顺序索引的比较散列与顺序索引的比较 v散列其实就是一种不通过值的比较，而通过值的含义来确定存储位置的方法，它是为有效地实现等值查询而设计的。v不幸的是，基于散列技术不支持范围检索。v而基于B+树的索引技术能有效地支持范围检索，并且它的等值检索效果也很好。v但是，散列技术在等值连接等操作中是很有用的，尤其是在索引嵌套循环连接方法中，基于散列的索引和基于B+树的索引在代价上的差别会很大散列与顺序索引的选择散列与顺序索引的选择v在实际的数据库设计中，

10、到底是用索引还是散列要充分考虑以下几个问题： 索引或散列的周期性重组的代价如何？ 在文件中插入和删除记录的频率如何？ 是否愿意以增加最坏情况下的访问时间为代价优化平均访问时间？ 用户可能提出哪些类型的查询？物理数据库设计物理数据库设计v数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。v为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程，就是数据库的物理设计。v目标： 提高数据库性能，以满足应用的性能需求； 有效利用存储空间； 在性能和代价之间做出最优平衡。v内容： 确定数据库的存储结构； 为数据选择合适的存取路径，即索引的设计； 对物理结构进行

11、评价，重点是评价时间和空间效率。 数据库的物理组织数据库的物理组织 v数据库的基础是基于操作系统的文件系统，对数据库的操作都要转化为对文件的操作，如何设计文件结构以及有效利用操作系统提供的文件存取方法是DBMS要考虑的事情。v因此，选定DBMS后，数据库物理组织的大概框架也就基本确定了，如一个数据库需要多少个文件，每个文件的作用是什么，等等。v关系数据库中要存储的数据主要包括：关系表、数据字典、索引、日志和备份等。DBMS对不同数据的物理组织方式通常是不一样的。确定数据库存储结构确定数据库存储结构 v确定数据存放位置 ：为了提高系统性能，数据应该根据应用情况将易变部分和稳定部分、经常存取部分和

12、存取频率较低部分分开来存放。v确定数据库存储结构 ：确定数据库存储结构时要综合考虑存取时间、存储空间利用率和维护代价三个方面的因素。这三个方面常常是相互矛盾的。例如，消除一切冗余数据虽然能够节约存储空间，但往往会导致检索代价的增加，因此必须进行权衡，选择一个折衷方案。确定数据存取路径确定数据存取路径 v在关系数据库中，选择存取路径主要是指确定如何建立索引。例如，应选择哪些属性作为搜索码建立索引，建立多少个索引，建立聚集索引(主索引)还是非聚集索引(辅助索引)，建立单码索引还是组合索引，等等。v常用的存储方式有三种：索引方法、聚集方法和Hash方法。目前使用最普遍的是B+树索引 。v关系数据库中

13、存取路径具有下列特点： 存取路径和数据是分离的； 存取路径可以由用户建立、删除，也可以由系统动态建立和删除； 存取路径的物理组织可以采用顺序文件、B+树文件或Hash文件。确定系统配置确定系统配置 v通常情况下，系统配置变量包括：同时使用数据库的用户数，同时打开数据库对象数，使用的缓冲区长度、个数，时间片大小，数据库的大小，装填因子，锁的数目等。这些参数值影响存取时间和存储空间的分配，在数据库物理设计时要根据应用环境确定这些参数值，以使系统性能最优。v注意，在数据库物理设计时对系统配置参数的调整只是初步的，在系统运行时还要根据系统实际运行情况做进一步的调整，以期切实改进系统性能。物理结构评价物

14、理结构评价 v数据库物理设计过程中，需要对时间效率、空间效率、维护代价和各种用户要求进行权衡，其结果可以产生多种方案。v数据库设计人员必须对这些方案进行细致的评价，从中选择一个较优的方案作为数据库的物理结构。v评价物理数据库的方法完全依赖于所选用的DBMS，主要是从定量估算各种方案的存储空间、存取时间和维护代价入手，对估算结果进行权衡、比较，选择出一个较优的合理的物理结构。如果该结构不符合用户需求，则需要修改设计。影响物理设计的主要因素影响物理设计的主要因素 v 应用处理需求。在进行数据库物理设计前，应先弄清应用的处理需求，如吞吐量、平均响应时间、系统负荷、事务类型及发生频率等，这些需求直接影响着设计方案的选择，而且它们还会随应用环境的变化而变化。v 数据特征。数据本身的特性对数据库物理设计也会有较大影响。如关系中每个属性值的分布、记录的长度与个数等，这些特性都影响到数据库的物理存储结构和存取路径的选择。v 运行环境。数据库物理设计与运行环境