kibot

Binary Search Algorithm for Market Data Files

This article is aimed at developers who need random-access-by-date into multi-gigabyte CSV tick files. binary_search.py is a Python module that locates a specific trading date inside a large sorted CSV by performing a binary search on byte positions rather than lines. It is part of the kibot-futures-library ecosystem and depends only on Python's standard library.

Overview

Financial tick files routinely reach multiple gigabytes and contain tens of millions of lines. A naive linear scan is impractical when you need to jump to a particular trading date. The module solves this by searching byte offsets directly: it reads small windows around the midpoint of the file, locates the nearest complete line, parses the leading date field, and narrows the range in the usual binary-search fashion. Any date is found in O(log n) time regardless of file size.

The module has zero external dependencies, it uses only os, datetime, and enum from the standard library.

Performance

The algorithm runs in O(log n) time complexity relative to file size. It reads only small buffers at each step rather than loading the file into memory, so RAM usage stays constant:

File Size Approximate Time
100 MB ~0.05 s
1 GB 0.1 -- 0.5 s
10 GB 0.5 -- 1.5 s

The forward-pass buffer is 500 to 2,000 bytes depending on file type; the refinement back-buffer runs up to 100,000 bytes for tick files. Memory consumption does not scale with file size.

Installation

binary_search.py ships as part of the kibot-futures-library package. To use it standalone, copy the file into your project and import directly:

from binary_search import find_position_in_file_binary, PositionFileType

Requirements: Python 3.6+ (the module uses f-strings). Standard library only.

API Reference

PositionFileType Enum

class PositionFileType(Enum):
 DAILY = 1
 INTRADAY = 2
 TICK = 3

This enum controls the buffer sizes used during the search. Choose the value that matches your file's line density:

Value Code Read Buffer Back Buffer Use Case
DAILY 1 500 bytes 1,000 bytes Daily OHLCV bars -- short, sparse lines
INTRADAY 2 2,000 bytes 100,000 bytes Minute/hour bars -- moderate density
TICK 3 2,000 bytes 100,000 bytes Tick-level data -- high density

The read buffer determines how many bytes are read at each binary search step to locate a complete line. The back buffer is used during the refinement pass to scan backward and find the first occurrence of the target date. For tick data, a single trading date can span hundreds of thousands of lines, so the larger back buffer ensures the refinement pass captures the true start of the date block.

find_position_in_file_binary()

def find_position_in_file_binary(
 file_name,
 date_to_find,
 file_type=PositionFileType.TICK,
 find_next_match=False,
 debug_callback=None,
 error_callback=None,
)

Parameters:

Parameter Type Default Description
file_name str (required) Absolute or relative path to the CSV data file.
date_to_find datetime.date or datetime.datetime (required) The target date to locate in the file.
file_type PositionFileType PositionFileType.TICK Controls buffer sizes. Set to match your file's data density.
find_next_match bool False When False, performs exact date match. When True, finds the first line with date >= target.
debug_callback callable or None None Optional function called with debug messages during the search. Signature: callback(message).
error_callback callable or None None Optional function called when non-fatal errors occur (e.g., decode failures on a line).

Returns a tuple:

Scenario Return Value
Date found (position, found_date, file_size)
Date not found (-1, None, file_size)
  • position (int), Byte offset from the start of the file where the first line of the target date begins. Use with file.seek(position) to jump directly to that point.
  • found_date (str), The date string as it appears in the file (MM/DD/YYYY), or None if not found.
  • file_size (int), Total size of the file in bytes. Useful for calculating how much data remains after the found position.

Search Modes

Exact Match (find_next_match=False)

The default mode. Returns the byte position of the first line matching the exact target date. If the date does not exist in the file (weekend, holiday, or simply not present), returns -1.

Typical uses: extracting all data for a specific trading date, validating that a particular date exists in a file, and jumping to a known date for inspection or repair.

Lower Bound / Ceiling (find_next_match=True)

Returns the byte position of the first line where the date is greater than or equal to the target. This is the more flexible mode and handles real-world scenarios where the exact date may not exist in the file.

Typical uses: finding the start of a date range when the start date might fall on a weekend or holiday (the search automatically lands on the next available trading day); building Continuous futures contracts where you need to splice data starting from a roll date that may not have tick data; and iterating through a file date-by-date without needing to know which dates have data.

Usage Examples

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

position, found_date, file_size = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 3, 15),
 file_type=PositionFileType.TICK,
)

if position >= 0:
 print(f"Found {found_date} at byte offset {position:,}")
 print(f"File size: {file_size:,} bytes")
else:
 print("Date not found in file")

Finding the Start Position of a Date Range

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

# Find the first available date on or after March 15
start_pos, start_date, _ = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 3, 15),
 file_type=PositionFileType.TICK,
 find_next_match=True, # lands on next trading day if 3/15 is missing
)

# Find the first date on or after March 22 (marks the end boundary)
end_pos, end_date, file_size = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 3, 22),
 file_type=PositionFileType.TICK,
 find_next_match=True,
)

if start_pos >= 0 and end_pos >= 0:
 print(f"Week of data: {start_date} to {end_date}")
 print(f"Byte range: {start_pos:,} to {end_pos:,} ({end_pos - start_pos:,} bytes)")

Using with Kibot Data Files

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

# Daily data -- use DAILY file type for smaller buffers
position, found_date, _ = find_position_in_file_binary(
 file_name="ES_daily.txt",
 date_to_find=date(2024, 1, 2),
 file_type=PositionFileType.DAILY,
)

# Intraday bars
position, found_date, _ = find_position_in_file_binary(
 file_name="ES_1min.txt",
 date_to_find=date(2024, 1, 2),
 file_type=PositionFileType.INTRADAY,
)

Processing Found Data

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

position, found_date, file_size = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 6, 10),
 file_type=PositionFileType.TICK,
)

if position >= 0:
 with open("ES_continuous.txt", "r") as f:
 f.seek(position)
 for line in f:
 # Each line: MM/DD/YYYY,HH:MM:SS,price,volume
 fields = line.strip().split(",")
 line_date = fields[0]

 # Stop when we reach a different date
 if line_date != found_date:
 break

 price = float(fields[2])
 volume = int(fields[3])
 print(f"{fields[0]} {fields[1]} price={price} vol={volume}")

How It Works

The algorithm operates directly on byte positions, treating the sorted CSV as a searchable byte stream. First, it initializes low = 0 and high = file_size. Then at each step it seeks to the midpoint mid = (low + high) // 2, reads forward until it hits a newline character, and parses the first 10 characters of the resulting line as an MM/DD/YYYY date. If the found date is earlier than the target it sets low = mid; if later it sets high = mid; otherwise the target has been located. Once the binary search converges, a refinement pass reads a back-buffer (up to 100,000 bytes for tick data) backward from the found position and scans it to locate the first line with the target date, ensuring the returned position points to the very beginning of the date block rather than somewhere in the middle.

The file is opened in binary mode (rb) for precise byte-level seeking; line content is decoded as ASCII for the date comparison. This avoids the overhead and unpredictability of text-mode line buffering on large files. Edge cases, empty files, lines too short to contain a date, and decode errors, are caught gracefully and routed through the optional error callback.

Input File Format

The module expects CSV files with the following characteristics: the date appears in the first field, formatted as MM/DD/YYYY (10 characters, zero-padded month and day); there is no header row (the first line of the file must be data); lines are chronologically sorted by date in ascending order (binary search requires sorted input); line terminators are \n or \r\n (both are handled); and fields are comma-separated.

Example lines (tick data):

03/15/2024,09:30:00,5200.25,150
03/15/2024,09:30:01,5200.50,75
03/15/2024,09:30:01,5200.25,200

Example lines (daily data):

03/15/2024,5198.50,5215.75,5190.00,5210.25,1845230
03/18/2024,5212.00,5225.00,5205.50,5220.75,1523440

See Data format reference for the full field layouts of every Kibot product.

Integration

binary_search.py is used across several tools in the Kibot data pipeline. kibot-gap-detector locates date boundaries when scanning for gaps in tick data. kibot-continuous-futures finds roll dates when splicing individual contract files into continuous series. Various data-repair tools use it to jump to specific dates for inspection and correction. The consistent (position, found_date, file_size) return format makes it straightforward to integrate anywhere random-access-by-date into sorted CSV files is needed.

Key Takeaways

  • O(log n) search by date in sorted CSV files; typical 10 GB file searched in 0.5-1.5 seconds.
  • Constant memory, reads small buffers (500-2,000 bytes forward, up to 100,000 bytes back) at each step.
  • Zero external dependencies; Python 3.6+ standard library only.
  • PositionFileType (DAILY/INTRADAY/TICK) tunes buffer sizes for the file's line density.
  • find_next_match=True gives lower-bound/ceiling semantics for date-range queries and roll-date logic.
  • Returns (byte_offset, date_string, file_size) or (-1, None, file_size) on miss; use file.seek(offset) to jump.
  • Requires files in MM/DD/YYYY,... format with no header and ascending date order.