索引技术

【概述】

在进行数据查找操作，当数据量不是很大时，一般的查找技术足以满足需求

但对于服务器来说，其是以大型数据库为中心的，并且其将大型数据库作为文件存放于外存中的，而当需要进行数据查找操作时，查找技术处理过于缓慢，为加快查找速度，设计出了索引这种结构

索引技术常应用于大型数据库与磁盘文件，通过索引可以实现对文件中记录的快速访问，对于一个文件来说，其可能拥有多个相关的索引，同时，每个索引往往只支持一个关键字

【基本概念】

关于索引技术的基本概念如下：

1. 文件：存储在外存上的数据的集合
2. 记录：由若干数据项组成的数据元素，是文件进行存取的基本单位
3. 数据项：数据记录中最基本的、不可分割的数据单位，是文件中可使用的最小单位
4. 索引：将关键码与其对应的记录相关联的过程，隶属于某一文件
5. 索引项：由关键码及关键码对应的记录在存取器中的位置等信息组成，是构成索引的基本单位

【索引的类型】

按照索引的结构是否可以改变，索引可以分为以下两类：

1. 静态索引：在文件创建时即生成索引结构，一旦生成就固定，只有当文件再组织时才发生改变
2. 动态索引：在文件创建时即生成索引结构，当文件执行插入、删除等操作时，索引结构随之改变

按照索引项组织的结构，索引可分为以下三类：

1. 线性索引：索引项组织为线性结构
2. 树形索引：索引项组织为树形结构
3. 多级索引：对于某些大型文件，其索引本身可能也很大，在这种情况下，可对索引再建一索引，从而构成多级索引结构

其中，线性索引是将索引项集合组织为线性结构，即索引表，其常见的形式有稠密索引、分块索引、倒排索引三种

进一步组，由于树结构每个结点可以存储一个元素，拥有多个孩子，那么在元素非常多的时候，就使得要么树的度非常大，要么树的高度非常大，这就使得在外存查找时，内存存取外存的次数非常多，严重影响了时间效率

为了提高时间效率，就要打破每一结点只能存储一个元素的限制，于是引入了多路查找树（Muitl-way Search Tree），其每一结点的孩子数可以多于两个，且每一结点可存储多个元素

而树形索引技术，就是将索引项组织为使用多路查找树的树形结构，其常见的形式有 2-3 树、2-3-4 树、B 树、B+树、B*树等