Amethyst DB - LSM Tree Database

A simple Log-Structured Merge Tree (LSM Tree) database implementation in Java.

Features

• MemTable: In-memory sorted data structure using ConcurrentSkipListMap
• SSTable: Immutable on-disk sorted tables
• Automatic Flushing: MemTable automatically flushes to disk when full
• Efficient Reads: Checks MemTable first, then SSTables from newest to oldest
• Persistence: Data persists across restarts

How to Run

Option 1: Using the provided script (Windows)

.\run.ps1

Option 2: Manual compilation and execution

# Compile
javac -d out -sourcepath src\main\java src\main\java\com\amethyst\db\*.java

# Run
java -cp out com.amethyst.db.Main

Usage

Commands

• put <key> <value> - Insert or update a key-value pair
• get <key> - Retrieve value for a key
• delete <key> - Delete a key (creates tombstone)
• stats - Show database statistics (MemTable, SSTables)
• flush - Force flush MemTable to disk
• demo - Run a demonstration
• help - Show help message
• exit - Exit the database

Example Session

amethyst> put name John
Inserting: name -> John
✓ Stored successfully

amethyst> put age 25
Inserting: age -> 25
✓ Stored successfully

amethyst> get name
Searching for key: name
  Found in MemTable
Value: John

amethyst> stats

=== LSM Tree Statistics ===
MemTable size: 2/5
Number of SSTables: 0

MemTable contents:
  age -> 25
  name -> John

amethyst> demo
(Runs a full demonstration of LSM Tree behavior)

How LSM Tree Works

1. Write Path: All writes go to the MemTable (in-memory sorted structure)
2. Flush: When MemTable reaches capacity (5 entries in this demo), it's flushed to disk as an immutable SSTable
3. Read Path: Reads check MemTable first, then search through SSTables from newest to oldest
4. Persistence: SSTables are stored in the data/ directory and persist across restarts

Project Structure

Amethyst_Db/
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── amethyst/
│                   └── db/
│                       ├── Entry.java      (Key-value entry)
│                       ├── MemTable.java   (In-memory table)
│                       ├── SSTable.java    (On-disk table)
│                       ├── LSMTree.java    (Main database engine)
│                       └── Main.java       (CLI interface)
├── data/                   (Created at runtime for SSTables)
├── out/                    (Compiled classes)
└── run.ps1                 (Run script)

Notes

• MemTable size is set to 5 entries for easy testing (see MEMTABLE_MAX_SIZE in Main.java)
• Data is stored in serialized format in the data/ directory
• This is a simplified implementation for educational purposes