数据库系统-学习记录10
ch3.索引结构
简介
稠密索引
在记录排好序时，可以在记录上建立稠密索引
键的顺序与文件中的排序顺序一致，图1为稠密索引的举例：
当索引文件中指向记录本身的指针长度远小于记录本身长度，以至于可以存入到内存时，优势就会非常明显：每次查询只需要使用一次I/O操作
使用稠密索引时，无需将索引放入内存即可知道文件是否存在。可以进行范围查询
稀疏索引
只为文件的每个存储块设一个键-指针对，节省了更多的存储空间，但查找给定值的记录需要更多时间
稀疏索引的举例如图2所示：
稀疏索引的优势：需要的空间更少，一次能够将更多的索引放入内存
多级索引
当索引可能占了多个存储块时，可以在索引上再进行索引（二级索引层）。二级索引明显比一级索引要少时，可以保存在内存中。如果二级索引仍然太大，还可以继续建立三级、四级索引层，直至能够存入内存
二级稀疏索引的举例如图3所示：
辅助索引
如图4所示，辅助索引不决定数据文件中记录的存放位置，仅表示当前记录的存储地址。即便索引是按顺序排列的，记录的存放也可以是无序的：
使用一个称作“桶”的间接层，可以避免索引的键值重复，如图5所示，索引的每个值，指向其在桶中第一次出现的位置：
使用辅助索引，可以在检索时，检索尽可能少的数据块
文档检索、倒排索引
在文档检索中，需要查询关键词出现在哪些文档中。可以使用如图6所示的称作倒排索引的索引（桶中存放的是指向相应文档中的相应位置的指针）：
之所以叫做倒排，是因为：原本是检索文档中出现哪些词，现在变为检索词出现在哪些文档中
B-树
相比于一级/两级索引，商用系统更多使用的是B-树及其变体B+树结构
B-树的结构
B-树将存储块组织为树的结构。此处的B-树与数据结构中的B-树相似，使用一个参数n来决定所有存储块的布局（在这里n为每个结点存储的查找键值的上限），例如，图7是一棵n=3的B-树：
在数据库的B-树索引中，主要是要尽量将n取得足够大
B-树的应用
B-/B+树的一系列指针，可以对应之前提到的任何一种索引：
B-树：稠密索引
B+树：稀疏索引
B-树的查找、范围查询、插入和删除
查找的过程与数据结构中所提及的是一致的，即从根结点出发，根据与结点中的各数值大小作比较，然后根据比较结果选择要进入到的子结点，直至到相应的叶结点进行最后的搜索
而范围查询则是在到达叶结点之后，在要查找的范围内，从左到右挨个搜索，直到正在搜索的这个叶结点存在大于b的键为止
而插入和删除，则需要根据B-树的定义，来考虑结点的合并与分裂
B-树的效率
通常情况下，数据库的一个索引只需要3层的B-树结构就足以表示全部信息。在参数n（B-树每个结点的键的上限）非常大的情况下，根结点几乎不会有任何改动，这时可以将根结点块永久地缓冲在主存中，以减少磁盘I/O次数，使其比3次还少
散列表（hash索引）
辅存散列表
包含大量记录的散列表需要存放在辅助存储器上，这样的散列表桶数组由存储块组成（而不是指向链表头的指针）。
散列表的结构如图8所示：
散列表的插入
在散列表的插入过程中，如果某个桶被装满，则新增溢出块到该桶的链上：
散列表的删除
同样地，如果要进行删除，在删除后那个桶不再溢出，则可以将溢出块删去，并将里面的元素移回前面的桶中
散列表索引的效率
当绝大多数的桶都只由单个块组成时，一般的查询只需要一次磁盘I/O，但随着文件增长，溢出块逐渐增多时，则读长链表需要更多次的磁盘I/O
可扩展散列表
可扩展散列表是一种动态散列方法，它用一个指向块的指针数组来表示桶，而不再是用数据块本身组成的数组来表示
可扩展散列表的结构如图9所示：
在图9中，可以注意到数据块的右上角方块中出现了1，表明存入的数据的前i位是用于确认是否能够获取存放到这个块中的资格的。例如，i=1时，桶中对应数字1的指针所指向的那个块，就是由第一位来进行判断的：首位为1的数据可以有资格放入这个块中
可扩展散列表的插入
在插入到的块中的空间已满时，需要对那个块进行分裂。分裂为两个块后，用于判断是否有资格进入到此块中的i位增加为i+1位，这样就可以保证数据被顺利地分到这两个块中
例如，在图9的基础上，插入一个数据1010。这是1开头的，故应该放入第二个数据块中，但注意到第二个数据块已经满了，因此需要对其进行分裂。首先，让数据块的右上角变为2，以表示用前两位来进行存放资格确认，随后将10开头的1001、正在插入的1010放入原有的块中，而11开头的1100则放入新增的块中。同时，i=1也应改为i=2，桶的数量也变为4个，分别表示00、01、10、11：
线性散列表
可扩展列表对空间的占用可能会非常地大，而使用线性散列的策略可以使桶的增长较为缓慢
在线性散列表中，会用参数i表示当前被使用的散列函数值的位数，参数n表示当前的桶数，参数r表示当前散列表中的记录总数。而比率r/n则会受到限制，从而使得桶数增长缓慢（此处允许有溢出块）
多维索引
从一维索引的散列表，推广到多维，有两种数据结构，分别为网格文件和分段散列函数：
网格文件
网格文件是将点空间划分为许多网格，随后分别将落入各区域的点存入相应的桶中：
分段散列函数
多维数据的树结构
多键索引
树的每一层的结点，都是一个属性的索引：
kd-树
所有维的属性在层间交替出现：
四叉树
在四叉树中，每个内部结点对应于k维空间中的k维立方体：
R-树
R-树表示由二维或更高维区域组成的数据，称之为数据区
位图索引
位图索引使用位向量表示数据出现的位置
位图索引的动机
位图索引允许我们在许多情形下高效地回答部分匹配査询
例如，有如下12条记录：
对于第一个分量，共有7种值，据此写出相应的7个向量（某个值相应的向量的第i位为1，表示在第i条记录中的该分量取这个值）：
而对于第二个分量，则有10种值，据此写出相应的10个向量：
现在要查询分量1位于45~55之间、分量2位于100~200之间的记录。首先对第一组向量中，45和50所对应的向量进行按位或运算，随后再对第二组向量中，100、110、120和140所对应的向量进行按位或运算，最后再对这两个结果进行按位与运算，所得向量中值为1的位，即为查询目标所在的位
压缩位图
向量过长，而1非常少时，可以考虑进行编码，以压缩位图
其中一种可行的方法：首先需要确定i的二进制表示是多少位，然后设置一个由（位数-1）个1和1个0所组成的二进制序列，再在它后面加上i的二进制表示
例如：i=13，则需要用4位二进制来表示i，因此先设置一个二进制序列1110（4-1=3个1），再在后面跟上13的二进制序列1101，即最后得到13的编码：11101101
反过来进行解码也是可行的：例如对于11101101001011，首先识别出1110，可以确定此数的二进制共有4位，因此再看随后4位，为1101，即第一个整数为13。再往后看，为0，即下一个数只有1位，而下一位还是0，因此第二个整数为0。继续往后看，为10，因此下一个数共有两位，为11，即第三个整数是3。综上所述，三个整数分别为13，0和3，这样也即完成了解码