-
Notifications
You must be signed in to change notification settings - Fork 32
/
2、索引及分类.md
193 lines (108 loc) · 9.63 KB
/
2、索引及分类.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#### 概述
索引
* 索引是定义在存储表(Table)基础之上，有助于无需检查所有记录而快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的索引项(indexentries)组成，每一索引项又由两部分构成:
* 索引字段：由Table中某些列(通常是一列)中的值串接而成。索引中通常存储了索引字段的每一个值(也有不是这样的)。
* 行指针：指向Table中包含索引字段值的记录在磁盘上的存储位置。
* 存储索引项的文件为索引文件，相对应，存储表又称为主文件
* 索引文件比主文件小很多。通过检索一个小的索引文件(可全部装载进内存)，快速定位后，再有针对性的读取非常大的主文件中的有关记录。
* 索引文件是一种辅助存储结构，其存在与否不改变存储表的物理存储结构；然而其存在，可以明显提高存储表的访问速度。
* 索引文件组织方式有两种：(相对照的有上面说的，主文件组织有堆文件、排序文件、散列文件、聚簇文件等多种方式)
* 排序索引文件(Orderedindices):按索引字段值的某一种顺序组织存储
* 散列索引文件(Hashindices):依据索引字段值使用散列函数分配散列桶的方式存储
* 在一个表上可以针对不同的属性或属性组合建立不同的索引文件，可建立多个索引文件。索引字段的值可以是Table中的任何一个属性的值或任何多个属性值的组合值
* 有索引时，更新操作必须同步更新索引文件和主文件。
* 衡量索引性能好坏：
* 访问时间
* 插入时间
* 删除时间
* 空间负载
* 支持存取的有效性,
SQL语言关于索引的基本知识
* 当定义Table后，如果定义了主键，则系统将自动创建主索引，利用主索引对Table进行快速定位、检索与更新操作;
* 索引可以由用户创建，也可以由用户撤消
* 当索引被创建后，无论是主索引，还是用户创建的索引，DBMS都将自动维护所有的索引，使其与Table保持一致，即：当一条记录被插入到Table中后，所有索引也自动的被更新
* 当Table被删除后(droptable),定义在该Table上的所有索引将自动被撤消，并删除相应索引文件
SQL语句
* 创建索引：
```sql
CREATE [unique] INDEX indexname
ON tablename ( colname [asc| desc]{, colname [asc| desc] . . .} );
```
* 示例：在student表中创建一个基于Sname的索引
```
create index idxSname on student(sname);
```
* 示例：在student表中创建一个基于Sname和Sclass的索引
```
create index idxSnamcl on student(sname, sclass);
```
* 撤消索引
```
DROP INDEX indexname;
```
* 对哪些属性建立索引
* 对经常出现在**检索条件**、**连接条件**、**分组计算条件**中的属性可建立索引
#### 分类
* 先说明一点，磁盘管理的最小单位是页，所以说索引指向记录，实际上也是索引指向记录所在的页
* 通过页头的行目录定位到记录，由于页头的行目录普遍也是稀疏的，所以如果还有剩余记录，还要再通过记录的记录头来进行判断，然后接着查找。
* 如果一个数据块有多个有被一个索引文件多次指向，那么就说明不是主文件不是按照索引字段聚簇存放的。
稠密索引与稀疏索
* 对于主文件中每一个记录(形成的每一个索引字段值)，都有一个索引项和它对应，指明该记录所在位置。这样的索引称稠密索引(denseindex)
* 对于主文件中部分记录(形成的索引字段值)，有索引项和它对应，这样的索引称非稠密索引(undense index)或稀疏索引(sparseindex)
* 稀疏索引如何定位记录
* 索引项不指向记录指针，而是指向记录所在存储块的指针，即**每一存储块有一个索引项**，而不是每条记录有一索引项----主索引
* 稀疏索引的使用要求—主文件必须是按对应索引字段属性排序存储
* 定位索引字段值为 K的记录，需要
* 首先找相邻的小于K的最大索引字段值所对应的索引项
* 从该索引项所对应的记录开始顺序进行Table的检索
* 相比稠密索引：空间占用更少，维护任务更轻，但速度更慢
* 索引文件中不存在搜索码的值，不代表主文件中没有对应搜索码的记录
* 稠密索引
* 先查索引，然后再依据索引读主文件
* 索引文件中不存在搜索码的值，就代表着主文件中没有对应搜索码的记录
* 分类（根据索引文件中索引字段在主文件中存放是否有序，即主文件的记录是否按该属性排序组织）
* 主文件记录按照索引字段排序组织（即按某属性聚簇存放的）
<img src="https://img-blog.csdnimg.cn/20201127093253382.png" width="50%" height="50%" />
* 主文件记录没有按照索引字段排序组织（无序就要考虑有无重复的情况）：允许索引包含重复值
<img src="https://img-blog.csdnimg.cn/20201127093308604.png" width="50%" height="50%" />
* 主文件记录没有按照索引字段排序组织（无序就要考虑有无重复的情况）：索引不包含重复值 + 指针桶（即多加了一层）
<img src="https://img-blog.csdnimg.cn/20201127093327471.png?" width="50%" height="50%" />
主索引与辅助索引
* 主索引通常是对每一存储块有一个索引项，**索引项的总数和存储表所占的存储块数目相同**，存储表的每一存储块的第一条记录，又称为锚记录(anchor record), 或简称为块锚(block anchor)
* 主索引的索引字段值为块锚的索引字段值，而指针指向其所在的存储块。
* 主索引是按索引字段值进行排序的一个有序文件，通常建立在有序主文件的基于主码的排序字段上，即主索引的索引字段与主文件的排序码(主码)有对应关系
* 主索引是稀疏索引。
* 辅助索引是定义在主文件的任一或多个非排序字段上的辅助存储结构。
* 辅助索引通常是对某一非排序字段上的每一个不同值有一个索引项：索引字段即是该字段的不同值，而指针则指向包含该记录的块或该记录本身；
* 当非排序字段为索引字段时，如该字段值不唯一，则要采用一个类似链表的结构来保存包含该字段值的所有记录的位置。
* 辅助索引是稠密索引，其检索效率有时相当高。
<img src="https://img-blog.csdnimg.cn/20201127093430301.png" width="50%" height="50%" />
* 主索引 vs. 辅助索引
* 一个主文件仅可以有一个主索引，但可以有多个辅助索引
* 主索引通常建立于主码/排序码上面；辅助索引建立于其他属性上面
* 可以利用主索引重新组织主文件数据，但辅助索引不能改变主文件数据
* 因为如果有主键，那么主文件的组织方式是按照主键的顺序有序排列的
* 没有主键一般是聚簇组织主文件
* 主索引是稀疏索引，辅助索引是稠密索引
聚簇索引和非聚簇索引
* 聚簇索引—是指索引中邻近的记录在主文件中也是临近存储的，也就是说索引项的顺序与表中记录的物理顺序一致
* 这里的物理连续一般很难做到，所以大都是通过每个数据块之间的双向指针连接，来保证逻辑上的顺序一致。
* **一个主文件只能有一个聚簇索引文件，但可以有多个非聚簇索引文件**，因为主文件最多只能指定一组排序属性，所以按照排序组织文件的话也就只有这一组属性的排序规则。
* 聚簇索引通常是**对聚簇字段上的每一个不同值有一个索引项（索引项的总数和主文件中聚簇字段上不同值的数目相同）**，索引字段即是聚簇字段的不同值，由于有相同聚簇字段值的记录可能存储于若干块中，则索引项的指针指向其中的第一个块。
<img src="https://img-blog.csdnimg.cn/20201127094046326.png" width="50%" height="50%" />
* 非聚簇索引—是指索引中邻近的记录在主文件中不一定是邻近存储的。
<img src="https://img-blog.csdnimg.cn/2020112709414023.png" width="50%" height="50%" />
* 聚簇索引有的 DBMS 不一定是默认建在主索引上，即不按主键来排序组织主文件
* 主索引通常是聚簇索引（但其索引项总数不一定和主文件中聚簇字段上不同值的数目相同，其和主文件存储块数目相同)；辅助索引通常是非聚簇索引。
* 主索引/聚簇索引是能够决定记录存储位置的索引；而非聚簇索引则只能用于查询，指出已存储记录的位置。
* 有些资料说叶子节点是数据节点的就称为聚簇索引，其实和这个是同一个意思，想表达就还是索引的顺序和数据组织的顺序相同。
倒排索引：文档专用的，通过关键词找文档
* 正排：一个文档包含了哪些词汇?#Doc1, { Word1,Word2,... }
* 倒排：一个词汇包含在哪些文档中Word1, { #Doc1, #Doc2, ... }
其他结构索引
* 多级索引：当索引项比较多时，可以对索引再建立索引，依此类推，形成多级索引
* 常见的多级索引形式，如B树/B+树索引，以树型数据结构来组织索引项等
* 多属性索引：索引字段由Table的多个属性值组合在一起形成的索引
* 散列索引：使用散列技术组织的索引
* 网格索引(Gridfile)：使用多索引字段进行交叉联合定位与检索