Page 88 - 《软件学报》2021年第5期

1312 Journal of Software 软件学报 Vol.32, No.5, May 2021

的内存空间.Entry 用于存储内存块在数据文件中的首地址以及 LogView 在块内的偏移量.图中 8byte 的前 40bit
用于存储内存块的首地址 headAddress,后 24bit 用于存储块内偏移量 offset.在计算机系统中,地址的编码是以字
24
节为最小单位,故 40bit 可表示最大 1TB 的磁盘文件大小;而后 24bit 用于存储块内偏移量,可表示 2 字节量大
18
小,而内存块的大小的初始值设置为 256KB(2 byte),所以 24bit 完全满足要求.

Fig.7 Creation and usage of indexing
图 7 索引的创建与使用
在理解一级索引与二级索引的结构之后,以一条 LogView 为例,说明索引的创建过程和索引的查询过程.
• 索引创建过程
在内存块写入数据文件中后,需要针对 LogView 的 id 创建索引并存储内存块在数据文件中的首地址和日
志在块内的偏移量.图 7 中可以清晰地看出一级索引与二级索引在内存中的关系,它们都在内存中的同一个字
节数组中,所以索引构建过程主要是对字节数组进行操作.创建索引的过程如下.
(1) 在根据 LogView 的 id 获取到 ip 与 index 值后,拼接“ip”与“index/4K”成为 8 字节的数据,表示为 A.
(2) 遍历所有一级索引 Entry 的值,如果存在与 A 值相等的数据,则直接返回对应 Entry 的位置 L;如果不存
在,则顺序添加一个新的 Entry 值 A,对应 Entry 的位置为 L,并创建一个对应 Segment 索引.
(3) 访问对应的(即第 L 个)二级 Segment 索引,其中具有 4K 个 Entry,计算 index%4K 的值为 T,则将对应
Segment 索引中第 T 个 Entry 空间用于存储块的首地址以及块内偏移量.
算法 2 的代码完整展示了索引创建中,字节数组的操作过程.
算法 2. 索引创建.
Input:
索引文件读取为完整的字节数组,每个元素(entry)占 8byte:array;
id 的组成部分:ip,index;
内存块首地址:headAddress;
LogView 在内存块中的偏移量:offset.
Output:
创建完成.
function createIndexing(array,ip,index,headAddress,offset)
Header←array[0:4K] //0~4K−1 的 Entry 为一级索引段
A←ip+index/4K //拼接 ip 与 index 的哈希值
addressInfo←headAddress+offset //高 40 位存首地址与第 20 位存偏移量信息
i←1