数据库上课第十一讲数据结构与索引

1、机械自动化学院机械自动化学院20152015主讲：主讲： 顾顾 曦曦 电话：电话：1569718107915697181079EmailEmail：主要内容文件、记录的组织索引B树索引散列物理数据库设计*2*31.1 存储介质的分类计算机的三级存储体系: 层次越高，每单位存储容量价格越贵，但速度越快存储易失性问题 ：易失性存储在设备断电后将丢失所有内容。一级存储为易失性存储，而二、三级存储系统都是非易失性存储。 1.2 磁盘*5扇区（section）： 磁盘上划分的区域 磁盘最小的物理存储单元 磁盘驱动器在向磁盘读取和写入数据时，以扇区为单位。 每个扇区可存放512个字节。磁盘块（block）

2、 文件系统层的概念，最小数据存储单元。 大小是扇区的2n倍磁盘的主要性能指标访问时间访问时间(access time):从发出读写请求到数据开始传输之间的时间。寻道时间寻道时间(seek time):为了访问(即读或写)磁盘上指定扇区的数据，磁盘臂磁盘臂移动以定位到正确的磁道所需的时间；旋转等待时间旋转等待时间(rotational latency time)：等待磁盘磁盘旋转直到指定的扇区出现在它下方所需的时间。访问时间访问时间=寻道时间寻道时间+旋转等待时间旋转等待时间磁盘的主要性能指标（续）数据传输率数据传输率(data-tranfer rate)从磁盘磁盘获得数据或者向磁盘磁盘存储数据

3、的速率。 磁盘的平均故障时间磁盘的平均故障时间(mean time to failure, MTTF)指磁盘无故障连续运行时间的平均值。*71.3 存储访问磁盘块(block)一个逻辑单元，它是包含固定数目的连续扇区。数据在磁盘和主存储器之间以块块为单位传输。缓冲区(buffers)主存储器中用于存储磁盘块磁盘块的副本的区域。缓冲区管理器：缓冲区管理器：负责缓冲区空间分配和管理的子系统；数据库系统通过缓冲区实现对磁盘上数据的存储访问。数据库系统的一个目的是减少磁盘和主存之间的传输。(1) 应用程序通过应用程序通过DML向向DBMS发出存取请求，发出存取请求，如如Select语句；语句；(2)

4、对命令进行语法检查对命令进行语法检查，正确后检查语义和用，正确后检查语义和用户权限（通过数据字典户权限（通过数据字典DD），并决定是否接），并决定是否接收；收；(3) 执行查询优化，将命执行查询优化，将命令转换成一串单记录的令转换成一串单记录的存取操作序列；存取操作序列；(4) 执行存取操作序列执行存取操作序列反复执行以下各步，反复执行以下各步，直到结束：直到结束：(5) 在缓冲区中找记录，若找到转在缓冲区中找记录，若找到转(10)，否则转，否则转(6)；(6) 查看存储模式，决定从哪个文件、用什么方式读取物理记录；查看存储模式，决定从哪个文件、用什么方式读取物理记录；(7) 根据根据(6)的

5、结果向操作系统的结果向操作系统(OS)发出读取记录的命令；发出读取记录的命令；(8) OS执行该命令，并读取记录数据；执行该命令，并读取记录数据；(9) 在在OS控制下，将读出的记录送入系统缓冲区；控制下，将读出的记录送入系统缓冲区；(10) RDBMS根据查询命令和根据查询命令和DD的内容导出用户所要读取的记录格式；的内容导出用户所要读取的记录格式；(11) RDBMS将数据从系统缓冲区中送入用户工作区；将数据从系统缓冲区中送入用户工作区；(12) RDBMS将执行状态信息将执行状态信息(成功或不成功等成功或不成功等)返回给应用程序；返回给应用程序；(13) 应用程序对工作区中读出的数据进行

6、相应处理。应用程序对工作区中读出的数据进行相应处理。存储访问的具体步骤：存储访问的具体步骤：1.4 定长记录与变长记录 文件在逻辑上可看作记录的序列记录的序列记录被映射到磁盘的物理块上。表示逻辑数据模型方式：1.4.1 定长记录定长记录定长记录指文件中所有记录均具有同样的字节长度同样的字节长度。*11存储Score记录的文件存在的两个问题：删除一条记录比较困难。要么填充被删空间，要么标记被删记录；除非块的大小恰好是记录大小的倍数，否则有的记录会跨块存跨块存储，储，会涉及两次磁盘I/O操作。 在文件开始处，分配一定数在文件开始处，分配一定数量的字节作为文件头量的字节作为文件头(file head

7、er)文件头中存储有关文件的各文件头中存储有关文件的各种信息。种信息。其中包括第一条被删除记录其中包括第一条被删除记录(即第一条可用记录即第一条可用记录)的地址。的地址。 处理办法：对被删除结点做标记，且使用空闲记录链表来管理记录的插入和删除；1.4.2 变长记录变长记录指文件中的记录具有不同的存储字节数。在数据库系统中，以下几种情况会导致使用变长记录： 多种记录类型(即多个关系表)在一个文件中存储； 允许记录类型中包含一个或多个变长字段； 允许记录类型中包含重复字段，如数组等。有多种变长记录的存储管理技术典型的有分槽页结构(slotted-page structure)分槽页结构一般用于在块

8、中组织记录。*14每个块的开始处有一个块头，块头中包含的信息有： 块头中已存储的条目(entry)个数个数#E(number of entries)； 块中空闲空间的末尾地址末尾地址EFS(end of free space)； 条目数组条目数组，其中每个条目中存储了该条目所对应变长记录的大小ES(entry size)和地址EP (entry pointer)。*15文件组织的常用方法2.1 堆文件组织 一条记录可以放在文件中的任何地方，只要那个地方有空间存放该记录。文件中的记录是没有顺序的，是堆积起来的。通常每个关系使用一个单独的文件。两种堆文件结构页链接式结构页目录结构*17首页数据页2

9、.2 顺序文件组织顺序文件是为了高效地按某个搜索码的顺序排序处理记录而设计的。为了快速地按搜索码搜索码的顺序获取记录，通常通过指针通过指针把记录逻辑上有序地链接起来逻辑上有序地链接起来。每个记录的指针指向搜索码顺序的下一条记录。在物理上按搜索码顺序按搜索码顺序或者尽可能地接近搜索码顺序存储记录，以减少顺序文件处理中磁盘块的访问数量。问题：插入、删除*18顺序文件中插入操作的处理在文件中定位，按搜索码顺序处于插入记录之前的那条记录（记为记录A）。如果记录A所在块中有空记录(可能删除后留下来的空间)，就在这里插入新的记录；否则将新记录插入在一个溢出块中。 搜索码与物理顺序不一致过多时，需重组，代价

10、较高。记录A2.3 多表聚集文件组织问题的提出：两个关系中作连接运算时，最坏的情况下，每个相匹配的记录都处在不同的磁盘块中，这将导致为获取所需的每一条记录都要读取一个磁盘块。 问题的解决 ：将两个关系的元组混合在一起聚集存储，从而支持高效的连接运算。如图7-8所示的两个关系，为了支持高效连接运算，可以采用图7-9所示的多表聚集文件结构。n 多表聚集文件组织多表聚集文件组织(Multitable Clustering File Organization)是是一种在每一个块中存储两个或多个关系的相关记录的文件结一种在每一个块中存储两个或多个关系的相关记录的文件结构。构。n 对于图对于图7-9所示的

11、所示的多表聚集文件结构多表聚集文件结构，可以加速特定连接的处，可以加速特定连接的处理，但是它将导致其它类型查询的处理变慢。在图理，但是它将导致其它类型查询的处理变慢。在图7-10中，中，通过指针将一个关系中的所有记录链接起来以方便查找。通过指针将一个关系中的所有记录链接起来以方便查找。 *213.0 索引的作用当表中有大量记录时，若要对表进行查询有两种方法：全表搜索：全表搜索：将所有记录一一取出，和查询条件进行一一对比，然后返回满足条件的记录，这样做会消耗大量数据库系统时间，并造成大量磁盘I/O操作；1.在表中建立索引在表中建立索引，然后在索引中找到符合查询条件的索引值，最后通过保存在索引中的

12、ROWID（相当于页码）快速找到表中对应的记录。索引的作用索引有助于更快地获取特定特定数据；保证数据记录的唯一性；实现表与表之间的参照完整性；在使用ORDER by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间。*233.1 基本概念 索引，使用索引可快速访问数据库表中的特定信息特定信息。索引是对数据库表中一列或多列的值进行排序进行排序的一种结构。索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针逻辑指针清单。在关系数据库中，索引是一种与表有关的数据库结构，它可以使对应于表的SQL语句执行得更快语句执行得

13、更快。基本概念搜索码搜索码(search key)：用于在文件中查找记录的属性属性或属性集属性集。经常需要在一个文件上建立多个索引，此时该文件就有多个搜索码。两种基本的索引类型：顺序索引顺序索引(ordered index)：基于搜索码的值的顺序排列，包括索引顺序文件和B+树索引文件等。散列索引散列索引(hash index)：通过搜索码值的散列函数(也称哈希函数)的值将所有记录平均、随机地分布到若干个散列桶中。基本概念索引文件索引文件：建立了索引的文件。索引文件中的记录自身可以按照某种排序顺序存储。一个索引文件可以有多个索引，分别对应于不同的搜索码。索引顺序文件索引顺序文件：根据主索引建立的

14、索引文件。主索引主索引(聚集索引聚集索引)：索引文件中的记录按照该搜索码值指定的顺序物理存储。辅助索引（非聚集索引）辅助索引（非聚集索引）：搜索码值顺序与索引文件中记录的物理顺序不同的那些索引。 3.2 索引技术的评价因素访问类型：索引能有效支持的数据访问类型。访问时间：通过索引找到一条特定记录或记录集所需要的时间。插入时间：在文件中插入一条新记录所需要的时间，包括找到插入新记录的正确位置和插入该记录所需要的时间以及更新索引结构所需要的时间。删除时间：在文件中删除一条记录所需要的时间，包括找到待删除记录的正确位置和删除该记录所需要的时间以及更新索引结构所需要的时间。空间开销：索引结构所需要的额

15、外存储空间。一般来说，索引是用空间代价来换取系统性能的提高，这就要进行空间与时间的折衷。3.3 聚集索引 （主索引）聚集索引中键值的逻辑顺序决定了表中相应行的物理顺序。聚集索引文件称为索引顺序文件。顺序索引有两类：稠密索引稠密索引。对应索引文件中搜索码的每一个值在索引中都有一个索引记录(或称为索引项)。每一个索引项包含搜索码值和指向具有该搜索码值的第一个数据记录的指针，如图7-11所示，其中studentName是搜索码。稀疏索引稀疏索引。稀疏索引只为索引文件中搜索码的某些值建立索引记录(或称为索引项)。每一个索引项包含搜索码值和指向具有该搜索码值的第一个数据记录的指针，如图7-12所示。多级

16、索引示例 即使采用稀疏索引，对于一个大型数据库而言，索引本身也可能变得很大。如果索引过大，主存中不可能读入所有的索引块，大部分索引块只能存储在磁盘上，这样在查询处理过程中，搜索索引就必须读大量的磁盘块。通过多级索引技术能够较好地解决上述问题。所谓多级索引就是在索引之上再建立索引。像对待其他顺序文件那样对待索引，在聚集索引上再构造一个稀疏索引，如图7-13所示。 事实上索引就是一个顺序文件，索引记录是按搜索码值有序存放的。3.5 索引的更新 删除记录 ：为了删除数据文件中的一条记录，系统首先要查找定位该记录，记待删除记录的搜索码值为KD。分稠密索引和稀疏索引来讨论。 对于稠密索引，如图7-11所

17、示， 索引更新的规则如下：如果被删除的记录是唯一具有KD值的记录，则从索引中删除相应的索引项(索引记录)，如删除“刘方晨”的记录。否则（即搜索码值为KD的记录有多条），采取如下操作：如果索引项中存储的指针指向待删除的记录，则更新该指针，使其指向文件中的下一条数据记录， 如删除学号为0701001的“李小勇”的记录；否则索引不必更新，如删除学号为0803025的“李小勇”的记录。对于稀疏索引，如图7-12所示，索引更新的规则：1、如果索引中不包含搜索码值为、如果索引中不包含搜索码值为KD的索引项，则索引不必更的索引项，则索引不必更新，新，如删除如删除“李小勇李小勇”、“王红敏王红敏”的记录的记录

18、。对于稀疏索引，如图7-12所示，索引更新的规则如下：2、否则（即索引中包含搜索码值为、否则（即索引中包含搜索码值为KD的索引项）的索引项）2.1 如果被删除的记录在数据文件中是唯一具有如果被删除的记录在数据文件中是唯一具有KD值的记录值的记录，采取如下操作：，采取如下操作：用数据文件中下一个搜索码值的记录更新该索引项用数据文件中下一个搜索码值的记录更新该索引项(包括搜索码值和指针包括搜索码值和指针都要更新都要更新)，如删除如删除“李宏冰李宏冰”的记录时用李小勇更新之的记录时用李小勇更新之；如果数据文件中下一个搜索码值的记录在索引中已经有一个索引项，则删如果数据文件中下一个搜索码值的记录在索引

19、中已经有一个索引项，则删除该索引项，除该索引项，如删除如删除“刘方晨刘方晨”的记录的记录。对于稀疏索引，如图7-12所示，索引更新的规则如下：2.2 否则否则(即索引中包含搜索码值为即索引中包含搜索码值为KD的索引项，且数据文件的索引项，且数据文件中包含多条搜索码值为中包含多条搜索码值为KD的记录的记录)，采取如下操作：，采取如下操作：如果索引项中存储的指针指向待删除的记录，则更新该指针如果索引项中存储的指针指向待删除的记录，则更新该指针，使其指向文件中的下一条数据记录，使其指向文件中的下一条数据记录，如删除学号为如删除学号为0701008的的“王王 红红”的记录的记录；否则索引不必更新，否则

20、索引不必更新，如删除学号为如删除学号为0703045的的“王王 红红”的记的记录录。 插入记录对于稠密索引，如图7-11所示。如果待插入记录的搜索码值不在索引中，则把该搜索码值插入到索引中，如插入一条姓名为“彭国强”的记录；否则索引不必更新，如插入一条学号为0701004、姓名为“王 红”的记录。对于稀疏索引，假设索引为每个块保存一个索引项。如果系统产生一个新块 (不是指溢出块)，将新块中第一条记录的搜索码值(即新块中最小的搜索码值)插入到索引中建立一个索引项，新建的索引项指向新块。如果没有新块产生，且插入记录在该块中具有最小的且唯一的搜索码值，则更新索引中指向该块的索引项的搜索码值；否则索引

21、不必更新。多级索引的插入和删除算法是对上述算法的一个简单扩充。在插入或删除时，对底层索引的更新如上所述。而对于第二层而言，底层索引就是一个包含索引记录的按搜索码值有序的顺序文件。因此，如果底层索引发生改变(插入或删除索引记录)，第二层索引就可以像上面描述的那样进行更新。如果还有更高层的索引，类似处理。3.6 非聚集索引（辅助索引）在数据文件中，记录按主索引而不是辅助索引的搜索码值顺序物理存储，因此具有同一个搜索码值同一个搜索码值的记录可能分布在文件的各个地方文件的各个地方。辅助索引必须是稠密索引辅助索引必须是稠密索引，即对于每个搜索码值都必须有一个索引项，而且该索引项要存放指向数据文件中具有该

22、搜索码值具有该搜索码值的所有记录所有记录的指针。指针桶即将数据文件中具有该搜索码值的所有记录的指针存放在一个指针桶中，索引项中的指针域再存放指向指针桶的指针(可以理解为指向指针数组的指针)。*38辅助索引在数据库更新的时候会增加很多开销直接使用辅助索引存在的问题原因：有些文件组织，即使记录本身没有更新，记录的位置也可能改变。比如说一个磁盘损坏了，我们将其存储的记录移动到新的磁盘。这个时候更新辅助索引很困难，因为每个磁盘存储了很多记录，而每个记录可能被分配到每个辅助索引的不同位置，这样一来，更新的代价就太大了，可能会涉及几十次的I/O访问。如何解决？在辅助索引中，不再存储指向所有记录的指针指向所

23、有记录的指针，而是存储主索引搜索码主索引搜索码的属性值。*39聚集索引和非聚集索引的使用动作描述使用聚集索引使用非聚集索引列经常被分组排序应应返回某范围内的数据应不应极少不同值不应不应小数目的不同值应不应大数目的不同值不应应频繁更新的列不应应外键列应应主键列应应频繁修改索引列不应应*403.7 索引的缺点索引需要占物理空间；随着文件的增大，索引查找的性能和数据顺序扫描的性能都会下降，可以通过对文件进行重组来改善。频繁地进行重组非常消耗资源。*424.1 B+树概述1）二叉二叉排序树排序树（Binary Sort Tree）：。所有非叶子结点至多拥有两个子（Left和Right）所有结点存储一个

24、关键字非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；经过多次插入与删除后，有可能导致不同的结构，甚至是线性的。平衡树(balanced search tree)对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。一般的查询复杂度是跟目标结点到树根的距离（即深度）有关如果可以让树维持矮矮胖胖的好身材(阶数2) , 完成上述工作就很省时间。能够一直维持好身材, 不因新增、删除而长歪的搜寻树, 叫做平衡树平衡树。*442）B-树1

25、970年，R.Bayer和E.mccreight提出了一种适用于查找的树，它是一种平衡的多叉树，称为B-树（或B树、B_树）。 所有关键字在整颗树中出现，且只出现一次只出现一次，非叶子结点可以命中；*453阶B树3）B+树在B-树基础上，为叶子结点增加链表指针链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中树总是到叶子结点才命中；*46稀疏索引稠密索引4）B*树*47在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；稀疏索引稠密索引4.2 B+树索引的结构 B+树索引是一个多级索引B+树索引采用平衡树平衡树结构，

26、即每个叶结点到根的路径长度相同。每个非叶结点有 n/2 到n个子结点，n对特定的树是固定的，称为阶数阶数。B+树索引中的所有结点的结构都相同树索引中的所有结点的结构都相同，它最多包含n-1个搜索码值，以及n个指针个指针每个结点中的搜索码值升序存放，即如果ij，那么KiKj。1）叶结点的结构对i=1, 2, , n-1，指针Pi指向具有搜索码值Ki的一条文件记录或指向一个指针桶，且指针桶中的每个指针指向具有搜索码值Ki的一条文件记录。指针Pn有特殊的作用。图7-16是Student文件的B+树索引的叶结点结构，搜索码为studentName。由于Student文件中的记录物理上直接按搜索码stu

27、dentName有序，所以叶结点中的指针直接指向文件的记录。各个叶结点中的搜索码值不重复且不相交B+树索引是稠密索引稠密索引，即数据文件中的所有互不相同的搜索码值必须在某个叶结点出现且只出现一次。每个叶结点中的搜索码值搜索码值升序排列升序排列可以利用各个叶结点的指针Pn将所有叶结点按搜索码值的排序顺序链接在一起。叶结点的链接排序能够高效地实现对数据文件的顺序顺序处理处理，而B+树索引中的其他结构能够高效地实现对数据文件的随机处理随机处理。B+树索引中的非叶结点非叶结点形成叶结点上的一个多级(稀疏)索引。非叶结点的结构与叶结点相同，只不过非叶结点中的所有指针都是指向B+树中下一层结点中下一层结点

28、的指针。每个非叶结点最多可存放n个指针个指针(对应于存放n-1个搜索码)，最少也要存放 n/2 个指针(对应于存放 (n-1)/2 个搜索码)。一个结点中存放的指针数称为该结点的扇出扇出。2）非叶结点的结构假设一个非叶结点中存放了m个指针， n/2 mn。若mnr/fr，其中nr表示将要存储的记录总数，fr表示一个桶中能存放的记录数目。偏斜。某些桶分配到的记录比其他桶多，所以，即使其他桶仍有空间，有些桶仍可能溢出，称为桶偏斜。偏斜发生的原因有两个：多个记录可能具有相同的搜索码值；所选择的散列函数可能会造成搜索码值的分布不均匀。桶溢出的处理桶溢出的处理方法：主要有闭散列和开散列二种方法。闭散列：

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

30、针组织成散列文件结构。散列索引的构建方法：将散列函数作用于一条文件记录的搜索码值，以确定索引项的散列桶；将由该搜索码值以及相应文件记录指针组成的索引项存入散列桶(或溢出桶)中。参见图7-22所示的Student文件的一个辅助散列索引散列索引散列索引散列索引只能是一种辅助索引结构。散列索引从来不需要作为主索引(聚集索引)来使用，因为一个文件如果自身是按散列组织的，就不必再在其上另外建立一个独立的散列索引了。不过，既然散列文件组织能像索引那样提供对记录的直接访问，不妨就认为以散列形式组织的文件上也有一个聚集散列索引了。 5.6 静态和动态散列 静态散列：在选择散列函数时就知道记录的总数，即桶的数量

31、必须事先确定。对于规模变化的数据库使用静态散列，有3种选择：根据当前文件大小选择散列函数。这种选择会使性能随数据库增大而下降。根据预计的将来某个时刻文件的大小选择散列函数。尽管这样可以一定程度上避免性能下降，但初始时会造成相当大的空间浪费。随着文件增大，周期性地对散列结构进行重组。重组是一个复杂、耗时的操作，而且重组期间必须禁止对文件的访问。动态散列技术允许散列函数动态改变，以适应数据库增大或缩小的需要。5.7 散列与顺序索引的比较 散列其实就是一种不通过值的比较，而通过值的含义值的含义来确定存储位置的方法，它是为有效地实现等值查询等值查询而设计的。散列技术在等值连接等操作中是很有用的，尤其是

32、在索引嵌套循环连接方法中，基于散列的索引和基于B+树的索引在代价上的差别会很大。基于散列技术不支持范围、最大最小值、排序的检索不支持范围、最大最小值、排序的检索。基于B+树的索引技术能有效地支持范围检索。选择散列与顺序索引时的考虑索引或散列的周期性重组的代价如何？在文件中插入和删除记录的频率如何？是否愿意以增加最坏情况下的访问时间为代价优化平均访问时间？用户可能提出哪些类型的查询？推荐读物*75数据结构与问题求解数据结构与问题求解(Java语言版语言版)(第第4版版)美 韦斯 (Mark Allen Weiss) 著, 葛秀慧 等 译清华大学出版社清华大学出版社 2011*76InnoDB数据

33、存储结构数据存储结构MySQL将所有数据都逻辑地存放在ib_data1文件中，称之为表空间。当然，也可以一个表对应一个物理文件（将innodb_file_per_table设置成ON）。表空间又划为成段，有数据段，索引段，回滚段。表空间由这些段和页组成。每段又划为成区，InnoDB每次最多可以申请4个区，即4M的存储空间。每个区又划为成页，一个区划分成64页，每个页的大小是16KB，大小不能够改，这也固定了一个区的大小为4M。页是MySQL操作的最小逻辑单位。*77InnoDB数据存储结构（续）数据存储结构（续）InnoDB是面向行的，这就意味着数据行存放在页中，每页最多能记录7992行数据。

34、MySQL定义了不同作用的页类型，比如B-Tree Page, Undo Log Page等，我们最关心的是B-Tree Page(数据页)。实际数据就以这样的页逻辑实体存在于表空间,总是以B+树结构索引组织的。换句话就说，实际数据一行一行地存放在B-Tree页中，这些页都放在数据段leaf node segment中。B-Tree Page是B+树的叶子节点。*78InnoDB数据存储结构（续）数据存储结构（续）一个B-Tree树，由7部分构成File Header，这里记录了页在表空间的一些信息，比如上一页，下一页，属于哪个表空间等等Page Header, 这里记录了页本身的一些存储信息

35、。比如第一个记录的位置，记录数，最后插入记录行的位置，该页的索引ID等等Infimum & Supermum Records, MySQL虚拟的二个行记录，用来界定记录的边界。分别代表此页中任何pk值还小的值和任何pk值还大的值。user records, 实际存储的行记录。*79InnoDB数据存储结构（续）数据存储结构（续）free space,空闲空间，同样是链表结构。当一个数据记录删除后，就会加入到空闲链表中page directory, 存放了记录的相对位置。注:聚集索引本身找不到具体的一条记录。而是通过 聚集索引找到该记录所在的页，然后再通过Page Directory进行二分查找

36、找到具体数据。File Trailer, MySQL InnoDB利用它来保证页完整地写入磁盘。*80索引的定义索引是加快数据检索的一种工具一张表可以建立多个索引，可从不同的角度加快查询速度；如果索引建立得较多，会给数据维护带来较大的系统开销。索引是由的记录构成索引逻辑上按照搜索码值进行排序，但不改变表中记录的物理顺序；索引和基本表分别存储。如在班级表中按所属学院建立的索引InstituteIdx，它与Class表之间的关系可以用图3-30来表示：*81数据库的索引一般按照B+树结构来组织，但也有Hash索引和位图索引等。索引的类型有聚集或非聚集两种，非聚集索引就是普通索引，一张表可以建立多个

37、普通索引。每张表仅能建立一个聚集索引聚集索引是按搜索码值的某种顺序(升序/降序)来重新组织表记录即索引的顺序就是表记录存放的顺序聚集索引可以极大地提高查询速度，但是给数据的修改带来困难一般建立了聚集索引的表不进行更新操作，仅执行查询操作，这在数据仓库中使用得较多。创建索引后，与该索引相关的描述信息会保存到数据字典中去。*82建立索引操作的语法 CREATE UNIQUE CLUSTERED | NONCLUSTERED INDEX ON ( ASC | DESC, ASC | DESC, ) ON *83其中：UNIQUE：表示建立唯一索引；CLUSTERED | NONCLUSTERED ：

38、表示建立聚集或非聚集索引，默认为非聚集索引；：索引的名称，索引是数据库中的对象，因此在一个数据库中必须唯一； ( ASC | DESC, ASC | DESC, )：指出为哪个表的哪些属性建立索引ASC | DESC为按升序还是降序建立索引，默认为升序；ON ：指定索引文件存放在哪个逻辑设备上，该逻辑设备必须是在创建数据库时定义的，或加入到数据库中的逻辑设备。缺省该项时自动将对象建立在主逻辑设备上。*84例3.72 在班级表中按所属学院建立一个非聚集索引InstituteIdxCREATE NONCLUSTERED INDEX InstituteIdx ON Class(institute)例

39、3.73 在学生表中，首先按班级编号的升序，然后按出生日期的降序降序建立一个非聚集索引ClassBirthIdx。CREATE INDEX ClassBirthIdx ON Student(classNo, birthday DESC)*85索引的删除索引一旦建立，用户不需要管理它，由系统自动维护；可删除那些不经常使用的索引；删除索引操作的语法为：DROP INDEX 删除索引时，系统会同时从系统的数据字典中将该索引的描述一起删除。例3.74 删除InstituteIdx索引。DROP INDEX InstituteIdx*86使用navCAT建立索引*87*88*89*90*917.0 数据

40、库的物理组织 数据库的基础是基于操作系统的文件系统，对数据库的操作都要转化为对文件的操作，如何设计文件结构以及有效利用操作系统提供的文件存取方法是DBMS要考虑的事情。关系数据库中要存储的数据主要包括：关系表、数据字典、索引、日志和备份等。DBMS对不同数据的物理组织方式通常是不一样的。7.1 物理数据库设计的概念数据库的物理结构数据库的物理结构数据库在物理设备上的存储结构存储结构与存取方法存取方法，它依赖于给定的计算机系统。数据库的物理设计数据库的物理设计为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程。物理数据库设计的目标和内容目标目标：提高数据库性能，以满足应用的性能需求；有效利用存储空间；在性能和代价之间做出最优平衡。内容内容：确定数据库的存储结构；为数据选择合适