文件的索引结构.ppt

《文件的索引结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、文件索引结构与倒排表2007/05/14本讲主要内容：平衡二叉树文件的索引结构倒排表与倒排索引类型无关的软件平台架构2字典的二分查找二分查找(binarysearch)要求：查找表为有序表，即表中结点按关键字有序排列，并且采用顺序存储结构。基本思想：确定搜索区间的中点位置：然后将待查的key值与range[mid].key比较：若相等，则查找成功并返回此位置，否则确定新的查找区间，继续二分查找.3动态查找表结构——二叉排序树（又称二叉搜索树）以关键码值为结点的二叉树如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根

2、结点的关键码；如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。101520406281530254二叉排序树的插入与构造如果二叉排序树为空，则新结点作为根结点。如果二叉排序树非空，则将新结点的关键码与根结点的关键码比较，若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到右子树中。子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为空二叉树，新结点插入成为叶子结点为止。5最佳二叉排序树的构造(1)先将字典元素关键码

3、排序。(2)对每个关键码按二分法在排序关键码序列中执行检索，将检索中遇到的还未在二叉排序树中的关键码插入二叉排序树中。——按二分查找中所遇到的节点依次插入二叉排序树。6举例（记录二分查找的过程）对于K={27,73,10,5,18,41,99,51,25}，构造最佳二叉排序树的过程如下：首先将它们排序为：5，10，18，25，27，41，51，73，99，然后从空二叉树出发，在排序的关键码序列中用二分法检索5，检索中遇到的结点为27,10,5，将这三个结点插入二叉排序树。再检索第二个结点10，遇到的结点为27,10，二叉排序树

4、中已经有这两个结点。再检索第三个结点18，…。得到的插入次序为27，10，5，18，25，51，41，73，99。7静态查找表索引结构scorestudentIDnameassignmentfinialexam4523周夏司50394616李景文1043472叶佩霖50354829郭舒文60514917杜文杰6052509阮萃茵7029513龙国才0355221陈俊珊45455313李欣怡7555554刘星50295728郭凌典25485914李敏妍90746127唐慰夷30496211吴宇翔0477110何英华0517830

5、梁迪欣80698索引索引是索引项的集合，一个索引项是由一个结点的关键码和该结点的存储位置组成的关联。索引的实质还是字典，而且是元素类型相同的等长结点的字典。所有关于字典的讨论都适合于索引；所有字典的实现也可以用来组织索引。9文件与索引结构——打开一个文件10从文本文件中读入数据集合11将数据集转换为记录集12通过记录的某一项属性值反过来查找到这个记录的存放地址，或者记录对应的关键码。我们称这种索引为倒排索引（invertedindex）。13倒排索引的建立14利用函数指针实现倒排索引的建立15包含数据逻辑层的软件架构数据源1数

6、据源2…数据源n数据逻辑层数据处理层数据结构及类型类型化计算数据对象XML文档+Stylesheet数据呈现数据交换16动态查找表——平衡二叉排序树以上的“最佳”二叉排序树，不仅构造的时间代价很大，而且很难动态的保持。通常用于表示一旦构造后就不改动的静态字典；对于动态字典，为了能够在进行元素的插入和删除操作时，较快地对二叉排序树进行调整，通常不要求二叉排序树总是保持“最佳的”检索效率，而是希望达到一种比较容易调整的“较佳”的状态。17平衡二叉排序树，又称AVL树，要求从整体上看，在动态插入或删除后，每个结点的左右子树能够基本保

7、持平衡。不会出现过分倾斜的现象，从而使得平均检索长度保持比较短。结点右子树高度与左子树高度之差称为该结点的平衡因子，平衡二叉排序树中每个结点的平衡因子只能是1、0或－1。1819插入的影响在平衡二叉排序树中插入新结点时，如果新结点插入后不影响其父结点为根的子树高度，则不会破坏整个二叉排序树的平衡；反之，若父结点为根的子树高度增加了，则可能引起一连串的反映。其结果又有两种可能，一种是在其祖先的某一层上不再影响子二叉排序树的高度，则整个二叉排序树仍然是平衡的；另一种是在其祖先的某一层上破坏了平衡的要求，使整个二叉排序树不再是AVL

8、树。20最小不平衡子树处理失去平衡的方法为首先找出最小不平衡子树（指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树），在保证排序树性质的前提下，调整最小不平衡子树中各结点的连接关系，以达到新的平衡。2122AVL树调整平衡的原则LL型调整破坏平衡的原因是由于在A的左