4索引结构解析.ppt

位图索引的诱因 位图索引主要在有多个码上的选择时对选择操作有用。 考虑一个选择收入在10000～19999之间的女性顾客的查询。在这个例子中，即Gender的位图F=（01101）和I-Level的位图L1＝（10100）的交得到位图00100，即第3个记录为要查询的记录。 位图的另外一个作用就是可以在不访问关系的条件下由位图索引计算出满足所给条件的元组数。如在本例中找有多少女性的收入水平为L2。 和实际关系相比，位图索引通常比较小。在位图中一位就可以代表一个记录。而且位的运算很容易在计算机中实现，执行起来效率比较高。 压缩位图（I） 假定在一个有n个记录的文件的字段F上建有位图索引，且在文件中出现的字段F不同的值是m。那么该索引的所有位向量的二进制位数就是m×n。 随着m的变大，位图索引所需的空间也就越多。但是，如果m很大，那么位向量的1将会很少。所以，我们有机会编码位向量以便它们平均占用的位比n少很多。 一个常用的方法叫做分段长度编码。 压缩位图（II） 分段长度编码 通过对整数i进行适当的二进制编码，得到一个由i个0且后跟一个1所组成的序列，这个序列表示一个段； 把每个段的代码拼接在一起，则得到整个位向量的编码。 对整数i的编码方法有多种，但要唯一的确定各个位向量。我们采用的方法如下： 首先需要确定i的二进制表示是多少位。假设数字j为log2i的上限，则i可表示为：（j-1个1和单个0） 然后，我们在它的后面加上i的二进制数。 如果i=13，那么j=4。即我们需要4位二进制来表示i。因此i的编码开始部分为1110。再把i的二进制数1101加上，则13的编码 压缩位图（III） 分段长度编码示例 位向量：100000001000，010000000100 分段长度序列（0，7），（1，7） 0的编码00，7的编码110111，1的编码01 编码位向量01110111 分段长度解码 向前扫描到第一个0并确定j的值。j等于我们找到第一个0所扫描过的位数（在计算位时包括0本身）。 一旦知道j，就查找后j位，该j位用二进制表示的数就是i。 重复以上过程，直至扫描完整个编码位向量。 分段长度解码示例 编码位向量：11101101001011 第四位为0，因而j=4，由下面4位1101得整数13。 同理可得分段长度序列（13，0，3）。 重新构造实际的位向量：0000000000000110001。 位图索引的管理（I） 查找位向量 把位向量看成记录，它们的键对应于该位向量的字段值。任何辅助索引技术都可以帮助我们有效地按值找到它们的位向量。 查找记录 一旦确定了我们所需要的数据文件中的记录为k，如何找到它？ 为记录号创建辅助索引，因为记录号从不改变（即使记录被删除也一样）。 数据文件修改的处理 一旦分配后，记录数必须保持一定。 数据文件的改变需要位图索引也作相应改变。 位图索引的管理（II） 删除记录 当我们删除记录i时，位图索引也必须改变，必须把位置i上为1的全部位向量把1改为0。 插入记录 对于每个位图索引，我们必须确定新记录在相应字段的值，并在该值的位向量后面追加1，在这个索引的其它位向量的末端加上一个新0。 若新记录有一个索引字段以前没有出现过值，则我们需要给这个值一个新的位向量。然后在这个索引的其它位向量的末端加上一位新0。 更新记录 把一个位图索引的字段的值从值v改为值w。我们必须找到v的位向量并把位置i上的1改为0。 如果存在一个值w的位向量，那么我们把它的位置i上的0改为1；如果不存在值w的位向量，那么创建一个新的位向量。 k-d树 k-d树是早期发明的一种用于多维检索的树结构，它每一层都根据特定的关键码将对象空间分解为两个部分。 顶层结点按一个维划分； 第二层结点按照另一维进行划分； …以此类推在各个维之间反复进行划分； 最终当一个结点中的点数少于给定的最大点数时，划分结束。 划分要使得在每个结点，大约一半存储在子树中的点落入一侧，而另一半落入另一侧。 k-d树的特点 k-d树是把二叉有哪些信誉好的足球投注网站树推广到多维数据的一种主存数据结构。 它的内部结点有一个相关联的属性a和一个值V，它将数据点分成两个部分：a值小于V的部分和a值大于等于V的部分。 由于所有维的属性在层间循环，所以树的不同层上的属性是不同的。 在一般的k-d树中，数据点存放在结点内，就像在二叉有哪些信誉好的足球投注网站树中一样。不过为了方便引入，我们做了以下修改： 内部结点只有一个该层属性的一个划分值和指向左、右子女的指针； 叶结点是块，每个块空间只能存放两条记录。 k-d树的例子 例：顾客数据库，假定相关的属性只有顾客的年龄和工资。示例数据库中有12个顾客。 (25， 60) (45， 60) (50，75)(50，10