What is Kafka's sparse index format and how does binary search work on it?

Each log segment has an offset index file (.index) whose entries map an offset, stored relative to the segment's base offset, to a physical position in the .log file. The index is sparse: it need not hold an entry for every message. A new entry is added roughly every index.interval.bytes of data (broker default log.index.interval.bytes = 4096 bytes), and the index file is pre-allocated up to segment.index.bytes (default 10 MiB). To find offset N: 1) pick the segment whose base offset is the largest one not above N. 2) Binary search the memory-mapped index for the greatest entry whose offset is less than or equal to N. 3) Seek to that physical position in the .log file and scan forward until offset N is reached. Because the index is sparse, the index files stay small while a lookup needs only a binary search plus a short scan.

Expected key concepts: physical position, log.index.interval.bytes, binary search, base offset, scan forward, .log file, memory-mapped