[管理学]第6章 数据库存储技术.ppt

6.4.1 索引技术 索引 主文件 图6.5 稠密索引示例 70 Wzbm 指针 ? Wzbm Wzmc Jldw Price 010101 010101 铍铜合金 Kg 010301 010301 铅锑合金 Kg 010401 010401 锆镁合金 Kg 020101 020101 25铜管材 根 020102 020102 20铜管材 根 020201 020201 25铝管材 根 020202 020202 10铝管材 根 60 80 90 1200 1000 800 6.4.1 索引技术 2. 辅助索引 由于主索引中具有相同索引项值的记录在同一地址或相邻地址中，因而查找速度慢，有时还需要使用辅助索引。采用辅助索引查找速度快，一般采用下面的方法：即仍采用索引记录（索引项值与对应的指针），不过此时指针指向的不是主文件记录地址而是指向一个桶（bucket），桶内存放指向具有同一索引项值的指针。如在前稀疏索引示例中，建立以Jldw为索引项的辅助索引。如图6.8所示，在这种结构中，以辅助索引为中介，可以通过二层指针方便地查到对应的主文件地址。 6.4.1 索引技术 1. B+树的结构 B+树索引是一个多级索引，但是其结构不同于多级索引顺序文件。B+树的索引结构是树的形式，最上一级索引是树的根结点，最下一级索引是树的叶结点。该级索引指针指向主文件的记录地址，一般采用稠密索引；而非叶的其他结点（包括根结点）的索引指向下一级结点的地址，一般为稀疏索引。 6.4.2 B+树索引文件 6.4.2 B+树索引文件 6.4.2 B+树索引文件 典型的B+树结点结构如图6.9所示，其中P为指针，K为索引项值，每个结点中的索引项值按次序存放，即如果ij，那么KiKj。 6.4.2 B+树索引文件 P1 K1 P2 K2 ? … Pi Ki ? … Pn-1 Kn-1 Pn 图6.9典型的B树结点 各叶结点中值的范围互不相交。因此，如果Li和Lj是两个叶结点，且ij，那么Li中所有的索引项值都小于Lj中的所有索引项值。既然叶结点指针指向主文件的记录地址，因此如要使叶结点是稠密索引，则每个索引项值都必须出现在某个叶结点中。在叶结点中指针Pn的作用是把叶结点按索引项顺序串在一起，即叶结点Li的Pn指向叶结点Li+1的第一个指针P1。 图6.10给出了一个B+树的例子，每个大写字母代表索引项值。为简单起见，省略了空指针和指向主记录的指针。 6.4.2 B+树索引文件 2. B树上的查询 假设要查询索引项值为K的所有记录，查询方法为： （1）检查根结点，找到大于K的最小索引值，假设为K，那么顺着P走到第二层结点。如果找不到这样的值，就沿着P走到第二层结点。 （2）在走到的第二层结点中用类似（1）的方法找到相应指针并到达第三层。 （3）如此重复，最终到达一个叶结点。如果该结点中有某个索引项值K等于K，那么指针P指向我们所需要的记录，如果在该叶结点中找不到值K，则不存在索引项值为K的记录。 6.4.2 B+树索引文件 提高数据库查找速度的另一种方法是散列（hash）技术。其基本原理是利用一种散列函数建立起主文件中指定项值与磁盘物理块间的映射联系，这样只要给出指定项的值立即可通过散列函数得到其对应的存储物理块地址。在对散列的描述中，将使用术语桶（bucket）来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块，但也可能小于或者大于一个磁盘块。 形式化地，令K表示所有指定项值的集合，令B表示所有桶地址的集合，散列函数H就是一个从K到B的函数。我们用H表示散列函数。 6.4.3 散列技术 散列技术的具体实现方法如下： （1）建立主文件的指定项K以及该项值的集合{ K1，K2… Kn}。 （2）建立磁盘物理存储单位桶以及桶地址的集合{B1，B2…Bn}。 （3）建立散列函数H（Ki），它建立主文件指定项的值与桶间的对应关系，对应一个Ki必通过H（Ki）找到惟一的一个桶地址。 6.4.3 散列技术 还可以将散列与索引相结合形成“散列索引”，从而使其效果更为有效。散列索引将索引项及相应指针组织成散列文件结构。散列索引的构造如下：将散列函数作用于索引项以确定对应的桶，然后将此索引项及相应指针存入此桶中。 例如，用图6.6中的主文件建立散列索引。以Wzbm为指定项，首先建立索引记录（见图6.6），所用散列函