在消息日志文件中以追加的方式存储着消息，每条消息都有着唯一的偏移量。在查找消息时，会借助索引文件进行查找。如果根据偏移量来查询，则会借助位移索引文件来定位消息的位置。为了便于讨论索引查询，下文都将基于位移索引这一背景。位移索引的本质是一个字节数组，其中存储着偏移量和相应的磁盘物理位置，这里偏移量和磁盘物理位置都固定用4个字节，可以看做是每8个字节一个key-value对，如下图：

索引的结构已经清楚了，下面就能正式进入本文的主题“二分查找”。给定索引项的数组和target偏移量，可写出如下代码：

1. private def indexSlotRangeFor(idx: ByteBuffer, target: Long, searchEntity: IndexSearchEntity): (Int, Int) = { 
2.   // _entries表示索引项的数量 
3.   // 1. 如果当前索引为空，直接返回(-1,-1)表示没找到 
4.   if (_entries == 0) 
5.     return (-1, -1) 
6.  
7.   // 2. 确保查找的偏移量不小于当前最小偏移量 
8.   if (compareIndexEntry(parseEntry(idx, 0), target, searchEntity) > 0) 
9.     return (-1, 0) 
10.    
11.   // 3. 执行二分查找算法，找出target 
12.   var lo = 0 
13.   var hi = _entries – 1 
14.   while (lo < hi) { 
15.     val mid = ceil(hi / 2.0 + lo / 2.0).toInt 
16.     val found = parseEntry(idx, mid) 
17.     val compareResult = compareIndexEntry(found, target, searchEntity) 
18.     if (compareResult > 0) 
19.       hi = mid – 1 
20.     else if (compareResult < 0) 
21.       lo = mid 
22.     else 
23.       return (mid, mid) 
24.   } 
25.    
26.   (lo, if (lo == _entries – 1) -1 else lo + 1) 
27. } 

上述代码使用了普通的二分查找，下面我们看下这样会存在什么问题。虽然每个索引项的大小是4B，但操作系统访问内存时的最小单元是页，一般是4KB，即4096B，会包含了512个索引项。而找出在索引中的指定偏移量，对于操作系统访问内存时则变成了找出指定偏移量所在的页。假设索引的大小有13个页，如下图所示：