硬件区域 12345…251252253254 次关键码1男 101111011 (性别 女 01 0 次类键吗2广东10010…0 (稀贯)[北京11111…00 上海00111 ●● 00 ●●。 次类键吗3建筑11001…0101… (专业)L讨算机_00111….001 电机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路静态搜索树 当数据对象数目特别大,索引表本身也很大, 在内存中放不下,需要分批多次读取外存才 能把索引表搜索一遍。 在此情况下,可以建立索引的索引,称为二 级索引。二级索引可以常驻内存,二级索引 中一个索引项对应一个索引块,登记该索引 块的最大关键码及该索引块的存储地址
(23,)(4,)(81,又 (06,/)(15,)(23,) (32,)(41,)(49,1) (6U0,/)(81,) head 020 6-5022-454-26叫 如果二级索引在内存中也放不下,需要分为许 多块多次从外存读入。可以建立二级索引的索 引,叫做三级索引。这时,访问外存次数等于 读入索引次数再加上1次读取对象。 必要的话,还可以有4级索引,5极索引,∴
这种多级索引结构形成一种m叉树。树中每 个分支结点表示一个索引块,它最多存放m 个索引项,每个索引项分别给出各子树结点 (低一级索引块)的最大关键码和结点地址。 树的叶结点中各索引项给出在数据表中存放的 对象的关键码和存放地址。这种m叉树用来作 为多级索引,就是m路搜索树 m路搜索树可能是静态索引结构,即结构在初 始创建,数据装入时就已经定型,在整个运行 期间,树的结构不发生变化。 m路搜索树还可能是动态索引结构,即在整个 系统运行期间,树的结构随数据的增删及时调 整,以保持最佳的搜索效率
max-heylobj-addr1 max- -key2obj-addr2...max- -keym obj-addrm 四级索引 三级索引 去已 000000000000000000000000-级索 亡自自亡自亡自亡亡自口数据区 多级索引结构形成m路搜索树