硬件区域 12345…251252253254 次关键码1男 10111 (性别)女 0 011 次关键码2广东10010…0 (籍贯)[北京11 e 11010 上海|00 次关键码3建筑11001…0101… (专业)计算机00 0011 电机10110 1010 单元式倒排表结构
硬 件 区 域 1 2 3 4 5 … 251 252 253 254 … 次关键码 1 男 1 0 1 1 1 … 1 0 1 1 … (性别) 女 1 1 1 1 1 … 0 1 1 0 … 次关键码 2 广东 1 0 0 1 0 … 0 1 0 0 … (籍贯) 北京 1 1 1 1 1 … 0 0 1 1 … 上海 0 0 1 1 1 … 1 1 0 0 … …… 次关键码 3 建筑 1 1 0 0 1 … 0 1 0 1 … (专业) 计算机 0 0 1 1 1 … 0 0 1 1 … 电机 1 0 1 1 0 … 1 0 1 0 … …… 单元式倒排表结构
如果在硬件区域1,……有要求的对象。然 后将硬件区城1,…等读入内存,在其中进 行检索,确定就可取出所需对象。 m路静态搜索树 当数据对象数目特别大,索引表本身也很大 在内存中放不下,需要分批多次读取外存才能 把索引表搜索一遍。 在此情况下,可以建立索引的索引,称为二级 索引。二级索引可以常驻内存,二级索引中 个索引项对应一个索引块,登记该索引块的最 大关键码及该索引块的存储地址
如果在硬件区域1，……中有要求的对象。然 后将硬件区域1，……等读入内存，在其中进 行检索，确定就可取出所需对象。 m路静态搜索树 当数据对象数目特别大，索引表本身也很大， 在内存中放不下，需要分批多次读取外存才能 把索引表搜索一遍。 在此情况下，可以建立索引的索引，称为二级 索引。二级索引可以常驻内存，二级索引中一 个索引项对应一个索引块，登记该索引块的最 大关键码及该索引块的存储地址
root (23,)(49,1)(81, (06,)(15,)(23,) (32,/)(41,)(49,) (60,/)(81,1) m山22m-- 如果二级索引在内存中也放不下,需要分为许 多块多次从外存读入。可以建立二级索引的索 引,叫做三级索引。这时,访问外存次数等于 读入索引次数再加上次读取对象。 必要的话,还可以有4级索引,5极索引,…
如果二级索引在内存中也放不下，需要分为许 多块多次从外存读入。可以建立二级索引的索 引，叫做三级索引。这时，访问外存次数等于 读入索引次数再加上1次读取对象。 必要的话，还可以有4级索引，5极索引，…
这种多级索引结构形成一种m叉树。树中每 个分支结点表示一个索引块,它最多存放m 个索引项,每个索引项分别给出各子树结点 (低一级索引块)的最大关键码和结点地址。 树的叶结点中各索引项给出在数据表中存放的 对象的关键码和存放地址。这种m叉树用来作 为多级索引,就是m路搜索树。 m搜索树可能是静态索引结构,即结枃在初 始创建,数据装入时就已经定型,在整个运行 期间,树的结构不发生变化。 m路搜索树还可能是动态索引结构,即在整个 系统运行期间,树的结构随数据的增删及时调 整,以保持最佳的搜索效率
这种多级索引结构形成一种 m 叉树。树中每 一个分支结点表示一个索引块，它最多存放m 个索引项，每个索引项分别给出各子树结点 (低一级索引块) 的最大关键码和结点地址。 树的叶结点中各索引项给出在数据表中存放的 对象的关键码和存放地址。这种m叉树用来作 为多级索引，就是m路搜索树。 m路搜索树可能是静态索引结构，即结构在初 始创建，数据装入时就已经定型，在整个运行 期间，树的结构不发生变化。 m路搜索树还可能是动态索引结构，即在整个 系统运行期间，树的结构随数据的增删及时调 整，以保持最佳的搜索效率
max-key1 obj-addr1 max 2 obj=addre ...max keym obj-addrm 四级索引 三级索引 级索引 000000絮引 d自自亡自亡数据区 多级索引结构形成m路搜索树
多级索引结构形成m路搜索树