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

Each partition segment has a .index file storing (relativeOffset, physicalPosition) pairs. The index is sparse — not every message gets an index entry, only one every log.index.interval.bytes (default 4KB of data). To find offset N: 1) Binary search in the .index file for the largest relativeOffset ≤ N. 2) Use its physicalPosition to seek in the .log file. 3) Scan forward from there until reaching offset N. The sparse index keeps index files small (fits in memory/page cache) while providing near-O(1) access to any offset.

Expected key concepts: sparse index, .index file, relativeOffset, physicalPosition, log.index.interval.bytes, binary search, scan forward, .log file, page cache, O(1) access