LSM Index Engine

A Java-based implementation of a Log-Structured Merge-tree (LSM-tree) storage engine with B+ tree indexing, designed for efficient data storage and retrieval of airport datasets.

Overview

This project implements a custom database storage engine that combines LSM-tree architecture with B+ tree indexes to provide fast write throughput and efficient range queries. The system is designed to handle airport data with support for primary and secondary indexes.

Features

• LSM-Tree Storage - Log-structured merge-tree implementation for optimized write performance
• B+ Tree Indexing - Efficient range queries and point lookups
• Persistent Storage - Data persistence with segment-based file storage
• Query Engine - Support for filtering, aggregations, and complex queries
• Memory-Optimized - Memtable and SSTable design for performance
• Compaction - Background compaction process to optimize storage

Architecture

Core Components

• LSM Index - Main indexing structure with memtable and SSTable segments
• B+ Tree - In-memory and persistent B+ tree implementation
• Query Engine - SQL-like query processing with filter and aggregation support
• Storage Layer - File-based persistence with schema management
• Result Sets - Multiple result set implementations (full scan, indexed, merged, intersect)

Data Model

The system works with airport data containing:

• Airport codes (IATA/ICAO)
• Geographic information (coordinates, elevation)
• Airport details (name, city, country)
• Operational data (timezone, DST)

Key Algorithms

LSM-Tree Operations

1. Write: Data inserted into memtable
2. Flush: Memtable written to disk as SSTable segment when threshold reached
3. Compaction: Merging of segments to optimize storage and query performance
4. Read: Query searches memtable first, then segments in reverse chronological order

B+ Tree Features

• Balanced tree structure for logarithmic search complexity
• Range query support with efficient leaf node traversal
• Sorted key storage for ordered iteration

Performance Characteristics

• Write Complexity: O(log n) for memtable insertion
• Read Complexity: O(log n) for indexed lookups
• Space Complexity: Optimized through periodic compaction
• Range Queries: Efficient through B+ tree leaf traversal

Data Files

• schema.txt - Table schema definition
• airports_original.txt - Airport dataset
• statements.txt - Sample query statements