索引存储结构

1、索引存储结构索引 索引 索引是一种允许直接访问数据表中某一数据行的树型结构，为了提高查询效率而引入，是一个独立于表的对象，可以存放在与表不同的表空间中。索引记录中存有索引关键字和指向表中数据的指针（地址）。对索引进行的I/O操作比对表进行操作要少很多。 索引的分类按逻辑设计分类：单列索引：基于一列的操作多列索引：组合索引，最多为32列。组合索引的列不一定与表中列顺序相同。惟一索引：列的值各不相同。非惟一索引：列的值允许相同。基于函数的惟一索引：利用表中一列或多列基于函数表达式所创建的索引。既可以是B-树，也可以是位图索引。按物理实现分类：分区或非分区索引，非分区既可以是B树，也可以是位图索引。

2、索引的存储方法 首先建立存储结点信息，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。如果每个节点在索引表中都有一个索引项，则该索引表就被称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表就成为稀疏索引。索引项的一般形式一般是关键字、地址。在搜索引擎中，需要按某些关键字的值来查找记录，为此可以按关键字建立索引，这种索引就叫做倒排索引，带有倒排索引的文件就叫做倒排索引文件，又称为倒排文件。倒排文件可以实现快速检索，这种索引存储方法是目前搜索引擎最常用的存储方法。索引结构的应用 索引结构能够在不断插入和删除记录的情况下保持良好的有效性，这对数据存储来说非常重要。 当今使用

3、的最广泛的就是一种被称为B+树的索引结构，它采用一种平衡树来组织索引项。在树中，内节点用于搜索导向,而叶节点则用来存储数据项。B+树是一种动态的索引结构，树的大小会因为数据项的多少而动态的增长或收缩；比如新的插入项或删除已有项，只会造成局部性调整，不会导致整个树结构重组。B+树主要特点和约束 树操作（插入/删除）能保持树平衡。搜索一个记录总是从树根节点开始，跨越树各层中的一个内节点到达叶节点。因为树是平衡的，所以从根节点到任一个叶节点路径都是等长的。 每个树节点用一个页来存储。 B+树节点可容纳的最大索引键值个数，称为B+树的阶数，通常以字母m表示。 除了根节点外，所有树节点都必须保持50%的

4、占有率。对阶数为m的B+树，非根节点中所包的索引键值个数j必须满足 m/2 j m。根节点是唯一可以不要求半满的节点，其索引键值个数j允许是1 j m。B+树的主要操作 B+数的搜索 B+树的检索有两种途径,一种从根开始进行随机查找,第二种是从最小关键字的left指针开始进行线性查找。这里我们采用第一种方式,检索分两个步骤:一、查找目标结点;二、在目标结点中查找关键字。B+树查找若在上层已找到待查关键码并不停止,而是继续沿着相应子树查到叶结点层为止。如果在叶结点的q找到k,则说明找到关键字,否则,没有找到。B+树的主要操作 B+树的插入在向数据库中插入新的数据时，同时也需要向数据库索引中插入相

5、应的索引键值，则需要向B+树中插入新的键值。以一棵3阶的B+树为例 ( 如左图 )。现在要向B+树中插入13和26两个数据。插入13时，要插入到第3层最左边的结点中。这个结点中恰好有空间，则直接插入即可。插入后的结果如右图 所示。B+树的主要操作 插入26时，则要插入到第3层的第2个结点中。这个结点没有空间，则要进行分裂。分裂成2个结点后, 要向其父结点中插入新的键值，而父结点也没有空间，则继续分裂，向根结点推进。结果如下图所示。B+数的主要操作 B+数的删除 当从数据库中删除数据时，同时也需要从数据库索引中删除相应的索引键值，则需要从B+树中删除该键值。从图1 所示的B+树中删除21这个键值

6、，则因为该结点的关键字数目大于2，则只需从该结点中直接删除该键值即可，结果如下图所示。B+树的主要应用 文本信息检索文本信息检索 NTFS文件系统文件系统 文件组织方面文件组织方面：对于文件组织来说，空间的利用非常重要。通过在分裂和合并时包含更多的兄弟节点，可以改善B+树的利用率。该技术可以同时用于根节点和叶节点。 文件存储：文件存储：1.文件很大，不可能全部存储在内存中，故要存储到磁盘上。2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数3.局部性原理与磁盘预读，预读的长度一般为页(page)的整倍数。4.数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。总结 综上所述，索引是影响数字数据库查找性