空间数据库索引技术PDF电子书下载

第1章　概述 1

1.1　数据对象与数据组织 1

1.2　数据库管理系统 3

1.3　数据库索引技术 5

1.4　空间数据库 6

1.5　空间数据库索引技术 8

1.6　时空数据库索引技术 9

1.7　本章小结 10

2.1　数据文件 12

第2章　数据存储 12

2.2　存储介质 13

2.2.1　主存储器 14

2.2.2　高速缓冲存储器 15

2.2.3　外部存储器 17

2.3　文件组织 22

2.3.1　顺序文件 22

2.3.2　索引文件 23

2.3.3　散列文件 26

2.4　本章小结 28

3.1　数据检索 29

第3章　数据检索及索引结构 29

3.2　静态检索 30

3.2.1　顺序检索 30

3.2.2　折半检索 32

3.2.3　索引顺序检索 34

3.3　动态检索 35

3.3.1　二叉检索树 35

3.4　基于哈希的检索 40

3.4.1　Hash表的基本概念 41

3.4.2　几种常用的Hash表 42

3.5　本章小结 47

第4章　数据库索引技术 48

4.1　DBMS中的数据检索 48

4.2　基于树的索引技术 49

4.2.1　索引顺序存取方法 49

4.2.2　B-树 51

4.2.3　B＋-树 53

4.3　基于哈希的索引技术 57

4.3.1　静态哈希 57

4.3.2　可扩展哈希 58

4.3.3　线性哈希 60

4.4　不同文件组织的性能比较 62

4.4.1　顺序文件的代价 62

4.4.2　排序文件 63

4.4.3　聚簇文件 64

4.4.4　基于树索引的顺序文件 65

4.4.5　基于哈希索引的顺序文件 65

4.4.6　I/O代价的比较 66

4.5　本章小结 67

5.1.1　空间数据特征 68

5.1　空间数据组织 68

第5章　空间数据库索引技术 68

5.1.2　空间数据模型 70

5.2　空间检索 75

5.2.1　空间查询 75

5.2.2 目标近似 76

5.2.3　基于目标近似的空间检索过程 77

5.3　空间索引 78

5.3.1　空间索引的需求 78

5.3.2　空间数据聚类 79

5.3.3　空间索引技术 81

5.4　本章小结 82

第6章　基于二叉树的空间索引 84

6.1　kd-树 84

6.1.1　kd-树的定义 84

6.1.2　kd-树的查找 85

6.1.3　kd-树的插入 85

6.1.4　kd-树的删除 86

6.1.5　分析 88

6.1.6　kd-树的变体 88

6.2　K-D-B-树 89

6.3　hB-树 90

6.4　hB＊-树 92

6.4.1　hB＊-树的基本特点 92

6.4.2　hB＊-树的插入和删除算法 92

6.4.3　分裂的避免 93

6.4.4　DAG的避免和消除 95

6.4.5　效果分析 98

6.5　本章小结 98

第7章　基于四叉树的空间索引 100

7.1　点四叉树 100

7.2.1　MX四叉树 101

7.2　区域四叉树 101

7.2.2　PR四叉树 102

7.3　CIF四叉树 102

7.4　本章小结 103

第8章　基于B-树的空间索引 104

8.1　R-树 104

8.1.1　R-树的定义 104

8.1.2　查找 105

8.1.3　插入 106

8.1.4　删除 108

8.1.5　分析 109

8.2　R＊-树 109

8.2.1　插入路径的选择 109

8.2.2　结点的分裂 110

8.2.3　强制重新插入 111

8.3　R＋-树 112

8.3.1　R＋-树及其特点 112

8.3.2　查找 113

8.3.3　插入 114

8.3.5　结点分裂 115

8.3.4　删除 115

8.4　本章小结 116

8.3.6　分析 116

第9章　基于动态哈希的格网法 118

9.1　网格文件 118

9.1.1　网格文件及其查找 118

9.1.2　插入 119

9.1.3　删除 120

9.1.4　分析 120

9.2　R-文件 120

9.3.1　G树的空间模型 121

9.3　G树 121

9.3.2　G树上的操作算法 123

9.3.3　G树的效率讨论 124

9.4　本章小结 124

第10章　基于空间目标排序的索引方法 125

10.1　Z-排序 125

10.2　Hilbert曲线 126

10.3　位置键 127

10.4　本章小结 128

11.1　QR-树的概念 129

第11章　QR-树 129

11.1.1　QR-树结点结构 130

11.1.2　QR-树类的设计 131

11.2　查找算法 136

11.2.1　查找算法描述 136

11.2.2　查找算法实现 137

11.3　插入算法 139

11.3.1　插入算法描述 139

11.3.2　插入算法实现 140

11.4.1　删除算法描述 141

11.4　删除算法 141

11.4.2　删除算法实现 142

11.5　本章小结 143

第12章　时空数据库索引技术 144

12.1　时空数据库 144

12.1.1　时空数据模型 144

12.1.2　移动数据对象 146

12.1.3　时空数据查询 147

12.2　时空数据库索引技术 147

12.3　基于离散数据表示的索引结构 148

12.3.1　3DR-树索引 148

12.3.2　RT-树索引 149

12.3.3　HR-树（History R-树） 150

12.3.4　小结 152

12.4　基于连续数据表示的索引结构 152

12.4.1　TPR树 152

12.4.2　PMR-Quad tree 157

12.4.3　Q+R树 161

12.4.4 IMORS 164

12.5　本章小结 169

13.1　商用数据库空间索引技术 171

13.1.1　Oracle Spatial的空间数据索引 171

第13章　空间数据库索引技术的应用与发展 171

13.1.2　IBM空间数据刀片（Spatial DataBlade） 173

13.1.3　MySQL空间数据扩展 173

13.1.4　ERSI空间数据引擎（Spatial Data Engine） 174

13.2　空间数据库索引技术的发展 175

13.2.1　高维空间索引技术 175

13.2.2　基于空间关系的索引技术 175

13.2.3　基于Web技术的空间索引技术 176

13.2.4　基于空间数据仓库的索引技术 176

13.3　本章小结 177

参考文献 179