1.1 序

存储结构由文件组成，这个文件的概念和操作系统的文件类似。一个数据可以存储一个关系，可能拥有一个或多个索引文件，每个索引文件建立查找建和数据记录之间的关联。查找键的指针指向与查找键具有相同属性值的记录。

2.1 索引的分类：

稠密索引：每个数据元祖都有一个索引，占据空间大，查找时间短。

稀疏索引：数据元祖分组，每一组有一个索引，占据空间相对小，查找时间相对长。稀疏索引只用于主键索引。

主键索引：通常建立在主键上，可以确定记录在数据文件中的位置。（决定是指数据在磁盘中的顺序和主键索引一致）

辅助索引：不能确定记录在数据文件中的位置。具体讨论见2.3

多级索引：在索引上增加索引，增加的索引一定是稀疏的，稠密没有意义。

默认数据库中关系元祖的记录是散布在各个块中的，如果遇到像select * from r这种查询必须要检索所有存储块。

稍微好的优化是为R预留一些数据块，甚至几个完整的柱面，这样不要扫描整个数据块就可以找到R中的所有元祖。

加了索引后，查询快，修改慢。索引建是排序的，所以每次U/D/I一条数据都会重新排序。

2.2 顺序文件

顺序文件是对关系中的元祖按主键进行排序而生成的文件。关系的元祖按照这个次序分布在多个数据块中。每次查询可以使用二分法查询。索引文件足够小，甚至可以存储在内存中而不用IO。

稠密索引

（一个框代表一个块。）

如图所示是一个稠密索引，索引文件智存储了索引字段的值。当扫描的时候只需要读取索引文件（文件小占据的块少，分布紧凑，读取快），然后知道所需要的文件的时候再根据索引建存储的指向，去找到需要的文件的记录。如果是稀疏索引，则每隔n个数据，再储存一次索引，查询时会用查询的数据和索引作比较，判断在哪个区间内。

2.3 辅助索引

由于顺序是由主键索引决定的，会根据主键索引去排序，所以辅助索引不能决定数据存储位置，只能用来查询数据存储的位置。也因此，辅助索引不能使用稀疏索引，因为区间的数值不一定在辅助索引规定的数值之间。

2.3 辅助索引

2.4 辅助索引的间接索引

间接索引

由于图2.3中的索引有多个索引都使用存储空间，浪费存储空间，所以可以使用如上的间接索引，类似稀疏索引，只是每个值都有索引，但是由于值重复，所以单个值也会形成区间。中间的桶文件是有序的。

多个辅助索引的查询

如果一个表有多个索引，这些索引刚好是查询条件，那么可以先根据索引找出两个索引指向的指针，在用指针去比对，找出符合条件的最终记录的地址，然后根据这个地址转换成物理地址，去磁盘上找出数据。

3.1 B-树

B-树是一颗平衡树，树根到树叶的所有路径一样长。由三部分组成，根，中间层，叶。

每个B-树索引都有一个参数n，这个参数决定了B-树的所有存储快布局。

每个存储快必须存放n个查找键和n+1个指针。在存储快能容纳n个键和n+1个指针的前提下，我们让n尽可能的大（不浪费空间）

例假设存储快的大小是4K，4096字节，整形数据占4个字节，指针占8个字节。则4n+8(n+1)<=4096  n最大值为340

B-树的规则

1、叶节点中的键是数据文件中的拷贝，从左到右排序在叶节点中。

2、根节点中至少有两个指针被使用，所有指针指向根节点下一层的存储块。

3.1常规B-树（n=3）

3.2 应用

1、B-树的查找键是数据文件的主键，且索引是稠密的，叶节点为数据文件中每条记录建立了键-指针  对。由于是稠密索引，数据文件可以主键排序也可以不排序

2、B+树是稀疏索引，数据文件主键排序。

3.3 B-树的查询

B-树的查询是递归的。以图3.1为例

例1查找5的节点

1、在根节点判断5<13，则进入左分支，遍历左侧的中间节点，得到7，5<7，进入7左侧的节点，遍历根节点，找到5节点。找到对应的指针，根据指针找到对应的数据。

例2查找10-25的节点

1、首先到达叶节点，查找到第二个节点里第一个键7小于10，第二个键11大于10，则设置起点为11

2、从起点向右，直到走到23时，依然小于25，走到29时，大于25，则记录下11到23的五个键的指针地址。去获取相应数据

3.4 B-树的插入

插入是一个递归分裂的过程，查询是从上到下直到找到根节点的递归，插入是从下到上直到有空间的递归。

1、首先判断叶节点是否有适当的空间存放新的键（正好在需要插入的位置上有空余空间）

2、如果没有，则分裂出一个新的节点空间，新的节点空间在上一层需要节点指向她，所以要查看上一层有没有空间，有的话则指向她，没有的话递归向上判断

3、如果一直到根节点仍然没有，则开辟一个新的节点与根节点并列，两个节点归属到同一个根节点下。

例 插入一个键为40的节点。

插入节点