第18讲——数据库索引

目录

第18讲——数据库索引

1.索引

1.1索引概念

1.2 索引特点

2.SQL语言中的索引创建与维护

2.1 SQL语言关于索引的基本知识

2.2 创建和维护索引的SQL语句

3.稠密索引与稀疏索引

3.1稠密索引

3.2 稀疏索引

4.主索引与辅助索引

4.1 主索引

4.2 辅助索引

4.3 主索引 vs 辅助索引

5.其他类型的索引

5.1 聚簇索引 vs 非聚簇索引

5.2 其他索引

6.B+树

7.散列索引

8.可扩展散列索引

9. 线性散列索引

1.索引

1.1索引概念

索引是定义在存储表(Table)基础之上，有助于无需检查所有记录而快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的索引项(indexentries)组成，

每一索引项又由两部分构成:

√索引字段:由Table中某些列(通常是一列)中的值串接而成。索引中通常存储了索引字段的每一个值(也有不是这样的)。索引字段类似于词典中的词条。

√行指针:指向Table中包含索引字段值的记录在磁盘上的存储位置。行指针类似于词条在书籍、词典中出现的页码。

存储索引项的文件为索引文件，相对应，存储表又称为主文件

索引文件组织方式有两种:

√排序索引文件(Ordered indices):按索引字段值的某一种顺序组织存储

√散列索引文件(Hash indices):依据索引字段值使用散列函数分配散列桶的方式存储

1.2 索引特点

●在一个表上可以针对不同的属性或属性组合建立不同的索引文件，可建立多个索引文件。索引字段的值可以是Table中的任何一个属性的值或任何多个属性值的组合值

●索引文件比主文件小很多。通过检索一个小的索引文件(可全部装载进内存)，快速定位后，再有针对性的读取非常大的主文件中的有关记录

●有索引时，更新操作必须同步更新索引文件和主文件。否则..

2.SQL语言中的索引创建与维护

2.1 SQL语言关于索引的基本知识

●当定义Table后，如果定义了主键，则系统将自动创建主索引，利用主索引对Table进行快速定位、检索与更新操作;

●索引可以由用户创建，也可以由用户撤消

●当索引被创建后，无论是主索引，还是用户创建的索引，DBMS都将自动维护所有的索引，使其与Table保持一致，即:当一条记录被插入到Table中后，所有索引也自动的被更新

●当Table被删除后(drop table)，定义在该Table上的所有索引将自动被撤消

2.2 创建和维护索引的SQL语句

3.稠密索引与稀疏索引

稠密索引:对于主文件中每一个记录(形成的每一个索引字段值)，都有一个索引项和它对应，指明该记录所在位置。这样的索引称稠密索引(dense index)

非稠密索引:对于主文件中部分记录(形成的索引字段值)，有索引项和它对应，这样的索引称非稠密索引(undense index)或稀疏索引(sparse index)

3.1稠密索引

3.2 稀疏索引

4.主索引与辅助索引

4.1 主索引

主索引通常是对每一存储块有一个索引项，索引项的总数和存储表所占的存储块数目相同，存储表的每一存储块的第一条记录，又称为锚记录(anchor record)，或简称为块锚(block anchor)

●主索引的索引字段值为块锚的索引字段值，而指针指向其所在的存储块。

●主索引是按索引字段值进行排序的一个有序文件，通常建立在有序主文件的基于主码的排序字段上，即主索引的索引字段与主文件的排序码(主码)有对应关系

●主索引是稀疏索引

4.2 辅助索引

辅助索引是定义在主文件的任一或多个非排序字段上的辅助存储结构。

●辅助索引通常是对某一非排序字段上的每一个不同值有一个索引项:索引字段即是该字段的不同值，而指针则指向包含该记录的块或该记录本身;

●当非排序字段为索引字段时，如该字段值不唯一，则要采用一个类似链表的结构来保存包含该字段值的所有记录的位置。

●辅助索引是稠密索引，其检索效率有时相当高。

4.3 主索引 vs 辅助索引

●一个主文件仅可以有一个主索引，但可以有多个辅助索引

●主索引通常建立于主码/排序码上面;辅助索引建立于其他属性上面

●可以利用主索引重新组织主文件数据，但辅助索引不能改变主文件数据

●主索引是稀疏索引，辅助索引是稠密索引

5.其他类型的索引

5.1 聚簇索引 vs 非聚簇索引

聚簇索引—是指索引中邻近的记录在主文件中也是临近存储的;

非聚簇索引—是指索引中邻近的记录在主文件中不一定是邻近存储的。

口 如果主文件的某一排序字段不是主码，则该字段上每个记录取值便不唯一，此时该字段被称为聚簇字段;聚簇索引通常是定义在聚簇字段上。

口 聚簇索引通常是对聚簇字段上的每一个不同值有一个索引项(索引项的总数和主文件中聚簇字段上不同值的数目相同），索引字段即是聚簇字段的不同值，由于有相同聚簇字段值的记录可能存储于若干块中，则索引项的指针指向其中的第一个块。

口 一个主文件只能有一个聚簇索引文件，但可以有多个非聚簇索引文件口，主索引通常是聚簇索引(但其索引项总数不一定和主文件中聚簇字段上不同值的数目相同，其和主文件存储块数目相同);辅助索引通常是非聚簇索引。

口 主索引/聚簇索引是能够决定记录存储位置的索引;而非聚簇索引则只能用于查询，指出已存储记录的位置。

5.2 其他索引

6.B+树

7.散列索引

1. 有M个桶，每个桶是有相同容量的存储地(可以是内存页，也可以是磁盘块)
2. 散列函数h(k)，可以将键值k映射到{0，1,..,M-1}中的某一个值
3. 将具有键值k的记录Record(k)存储在对应h(k)编号的桶中

• 目标:选择一个合适的散列函数，将一个Record集合(每个Record都包含一个关键字k)均匀地映射到M个桶中。即:对于集合中任一个关键字，经散列函数映射到地址集合中任何一个地址的概率是近乎相等的。
• 内存数据可采用散列确定存储页，主文件可采用散列确定存储块，索引亦可采用散列确定索引项的存储块
   
• M个桶。一个桶可以是一个存储块，亦可是若干个连续的存储块。

8.可扩展散列索引

• 为桶引入一间接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶
• ·指针数组能增长，其长度总是2的幂。因而数组每增长一次,桶的数目就翻倍。不过，并非每个桶都有一个数据块;如果某些桶中的所有记录可以放在一个块中，则这些桶可能共享一个块。
• ·散列函数h为每个键计算出一个K位二进制序列，该K足够大，比如32。但是桶的数目总是使用从序列第一位或最后一位算起的若干位，此位数小于K,比如说i位。也就是说，当i是使用的位数时,桶数组将有2i个项。

9. 线性散列索引

• 桶数n的选择总是使存储块的平均记录数保持与存储块所能容纳的记录总数成一个固定的比例，例如80%。超过此比例，则桶数增长1块，分裂。---线性增长，每次增1。
• 存储块并不总是可以分裂，所以允许有溢出块，尽管每个桶的平均溢出块数远小于1。
• 用来做桶数组项序号的二进制位数是[ log2nl，其中n是当前的桶数。这些位总是从散列函数得到的位序列的右端(即低位)开始取。