第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