索引存储结构资料.ppt

索引存储结构 索引 索引索引是一种允许直接访问数据表中某一数据行的树型结构 为了提高查询效率而引入 是一个独立于表的对象 可以存放在与表不同的表空间中 索引记录中存有索引关键字和指向表中数据的指针 地址 对索引进行的I O操作比对表进行操作要少很多 索引的分类 按逻辑设计分类 单列索引 基于一列的操作多列索引 组合索引 最多为32列 组合索引的列不一定与表中列顺序相同 惟一索引 列的值各不相同 非惟一索引 列的值允许相同 基于函数的惟一索引 利用表中一列或多列基于函数表达式所创建的索引 既可以是B 树 也可以是位图索引 按物理实现分类 分区或非分区索引 非分区既可以是B 树 也可以是位图索引 索引的存储方法 首先建立存储结点信息 还建立附加的索引表来标识结点的地址 索引表由若干索引项组成 如果每个节点在索引表中都有一个索引项 则该索引表就被称为稠密索引 若一组节点在索引表中只对应于一个索引项 则该索引表就成为稀疏索引 索引项的一般形式一般是关键字 地址 在搜索引擎中 需要按某些关键字的值来查找记录 为此可以按关键字建立索引 这种索引就叫做倒排索引 带有倒排索引的文件就叫做倒排索引文件 又称为倒排文件 倒排文件可以实现快速检索 这种索引存储方法是目前搜索引擎最常用的存储方法 索引结构的应用 索引结构能够在不断插入和删除记录的情况下保持良好的有效性 这对数据存储来说非常重要 当今使用的最广泛的就是一种被称为B 树的索引结构 它采用一种平衡树来组织索引项 在树中 内节点用于搜索导向 而叶节点则用来存储数据项 B 树是一种动态的索引结构 树的大小会因为数据项的多少而动态的增长或收缩 比如新的插入项或删除已有项 只会造成局部性调整 不会导致整个树结构重组 B 树主要特点和约束 树操作 插入 删除 能保持树平衡 搜索一个记录总是从树根节点开始 跨越树各层中的一个内节点到达叶节点 因为树是平衡的 所以从根节点到任一个叶节点路径都是等长的 每个树节点用一个页来存储 B 树节点可容纳的最大索引键值个数 称为B 树的阶数 通常以字母m表示 除了根节点外 所有树节点都必须保持50 的占有率 对阶数为m的B 树 非根节点中所包的索引键值个数j必须满足 m 2 j m 根节点是唯一可以不要求半满的节点 其索引键值个数j允许是1 j m B 树的主要操作 B 数的搜索B 树的检索有两种途径 一种从根开始进行随机查找 第二种是从最小关键字的left指针开始进行线性查找 这里我们采用第一种方式 检索分两个步骤 一 查找目标结点 二 在目标结点中查找关键字 B 树查找若在上层已找到待查关键码并不停止 而是继续沿着相应子树查到叶结点层为止 如果在叶结点的q找到k 则说明找到关键字 否则 没有找到 B 树的主要操作 B 树的插入在向数据库中插入新的数据时 同时也需要向数据库索引中插入相应的索引键值 则需要向B 树中插入新的键值 以一棵3阶的B 树为例 如左图 现在要向B 树中插入13和26两个数据 插入13时 要插入到第3层最左边的结点中 这个结点中恰好有空间 则直接插入即可 插入后的结果如右图所示 B 树的主要操作 插入26时 则要插入到第3层的第2个结点中 这个结点没有空间 则要进行分裂 分裂成2个结点后 要向其父结点中插入新的键值 而父结点也没有空间 则继续分裂 向根结点推进 结果如下图所示 B 数的主要操作 B 数的删除当从数据库中删除数据时 同时也需要从数据库索引中删除相应的索引键值 则需要从B 树中删除该键值 从图1所示的B 树中删除21这个键值 则因为该结点的关键字数目大于2 则只需从该结点中直接删除该键值即可 结果如下图所示 B 树的主要应用 文本信息检索NTFS文件系统文件组织方面 对于文件组织来说 空间的利用非常重要 通过在分裂和合并时包含更多的兄弟节点 可以改善B 树的利用率 该技术可以同时用于根节点和叶节点 文件存储 1 文件很大 不可能全部存储在内存中 故要存储到磁盘上 2 索引的结构组织要尽量减少查找过程中磁盘I O的存取次数3 局部性原理与磁盘预读 预读的长度一般为页 page 的整倍数 4 数据库系统巧妙利用了磁盘预读原理 将一个节点的大小设为等于一个页 这样每个节点只需要一次I O就可以完全载入 总结 综上所述 索引是影响数字数据库查找性能因素之一 较好的索引机制可提高检索数据速度 并能提高数据空间利用率上述所说的优点也是索引技术广泛应用于数据库中数字数据的搜索查询的原因 如SQLServer MySQL Oracle等等 人有了知识 就会具备各种分析能力 明辨是非的能力 所以我们要勤恳读书 广泛阅读 古人说 书中自有黄金屋 通过阅读科技书籍 我