数据库系统实现——索引结构

    xiaoxiao2021-03-25  51

    一 概述

    索引的目的:按给定查找键值快速定位记录。

    二 顺序文件上的索引

    2.1 顺序文件

    2.1.1 概念

    记录按查找键排序(可二分查找)。

    2.1.2 密集索引

    概念:每个记录都有一个索引项,索引项按查找键排序。

    查找方法:查找索引项,跟踪指针即可

    为什么使用密集索引:记录通常比索引项大->索引可以常驻内存,可在内存进行查找。

    缺点:索引占太多空间。

    2.1.3 稀疏索引

    概念:仅部分记录有索引项,一般为每个数据块的第一个记录建立索引。

    优点:节省索引空间

    缺点:查找需要访问磁盘(在内存找到所要查找记录所在块,到磁盘中将该块取到内存再查找)

    2.1.4 多级索引

    一级索引太大不能放内存的话,可以把二级索引放内存。

    二级索引仅可用稀疏索引。

    一般不考虑三级以上索引——应该用红黑树

    三 辅助索引

    3.1 概念

    主索引:顺序文件上的索引;记录按索引属性值有序;根据索引值可以确定记录的位置。

    辅助索引:数据文件不需要按查找键有序;根据索引值不能确定记录在文件中的顺序;辅助索引只能是密集索引(无序)。

    3.2 辅助索引重复键值处理

    采用间接桶(介于辅助索引和间接桶之间)

    3.3 倒排索引

    应用于文档检索,与辅助索引思想类似。

    思想:为每个检索词建立间接桶,桶的指针指向索引词所出现的文档。

    四 B+树

    4.1 概念

    一种树形的多级索引结构;

    所有节点为n个值,n+1个指针;

    所有叶节点位于同一层;

    适用于主索引,也适用于辅助索引

    4.2 查找

    从根节点开始;

    沿指针向下,直达到达叶节点;

    在叶节点书序查找。

    4.3 插入和删除

    见相关数据机构书籍。

    4.4 效率分析

    IO代价等于树高(通常不超3层,且根节点常驻内存,则IO=2)

    五 散列表

    思想:给定一个查找键k,对应的记录必定位于桶h(k)中;

    文件增长解决方法:

    动态散列表:可扩展散列表——成倍增加桶的数目;线性散列表——线性增加;

    六 实例研究

    MySQL索引研究见下一篇博客。

    转载请注明原文地址: https://ju.6miu.com/read-50326.html

    最新回复(0)