# GrayDB

**Repository Path**: wanghuiyao/gray-db

## Basic Information

- **Project Name**: GrayDB
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-07-07
- **Last Updated**: 2026-07-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

<div align="center">

# GrayDB

</div>

> Lightweight, embeddable, memory-only database engine written in C++17 — B+tree, hash index, custom SQL dialect, and interactive REPL.

---

## Overview

**GrayDB** is a minimal, high-performance embedded database engine rewritten in **C++17**. It uses a B+tree primary key index with secondary index support, a hash index for key-value lookups, and a recursive-descent SQL parser with an interactive REPL.

All data lives in RAM — no persistence, no network, single-threaded. Designed for learning, extensibility, and experimentation.

---

## Features

- **B+tree Primary Key Index** — automatic PK index on column 0, with leaf-chain range scans
- **Secondary Indexes** — `CREATE INDEX ON table (col)`, backed by B+tree
- **Hash Index** — open-addressing hash table for point lookups
- **Range Queries** — `WHERE id > 10 AND id < 20` via B+tree leaf chain
- **Custom SQL Dialect** — `CREATE TABLE`, `INSERT`, `SELECT`, `DELETE`, `CREATE INDEX`
- **REPL with Readline** — interactive shell with history; fgets fallback
- **Type System** — INT, FLOAT, STRING, BOOL, DATE (`variant`-backed)
- **Row Freelist** — LIFO hole reuse on DELETE → O(1) insert
- **GoogleTest Suite** — 232 test cases, 6 suites, 100% pass

---

## Architecture

```
src/
├── main.cpp               # 入口
├── cli/
│   ├── repl.hpp/cpp        # REPL 循环 (readline/fgets)
│   └── parser.hpp/cpp      # 递归下降 SQL 解析器
├── database/
│   ├── database.hpp/cpp    # Database 类 (多表管理)
│   └── table.hpp/cpp       # Table 类 (行存储 + 索引)
├── index/
│   ├── index.hpp           # Index 抽象基类
│   ├── bptree_index.hpp    # B+ 树索引模板 (header-only, Order=4)
│   └── hash_index.hpp      # 哈希索引模板 (header-only)
└── storage/
    ├── value.hpp/cpp        # Value = variant<int32_t,float,string,bool,Date>
    ├── row.hpp/cpp          # Row = vector<Value>
    └── schema.hpp/cpp       # Schema / ColumnDef
```

- **Row storage**: `vector<optional<Row>>`, `row_id` ≡ array index
- **Index decoupling**: indexes store `row_id_t` (uint64), not raw pointers
- **Memory-only**: all data in RAM, single-threaded, no locks

---

## Build

### CMake (recommended)

```bash
cmake -S . -B build -G "MinGW Makefiles"    # Windows: MinGW Makefiles
cmake --build build                          # compile → build/graydb(.exe)

# Run tests
cd build && ctest --output-on-failure
```

**Readline**: auto-detected. Install via MSYS2 (`pacman -S mingw-w64-x86_64-readline`) or Strawberry Perl. Falls back to `fgets` if not found.

---

## Usage

```
Welcome to GrayDB!

graydb> CREATE TABLE users (id INT, name STRING, age INT);
graydb> INSERT INTO users VALUES (1, "Alice", 25);
graydb> INSERT INTO users VALUES (2, "Bob", 30);
graydb> SELECT * FROM users WHERE id > 0 AND id < 5;
graydb> CREATE INDEX ON users (age);
graydb> SELECT * FROM users WHERE age = 25;
graydb> DELETE FROM users WHERE id = 2;
graydb> EXIT
```

---

## SQL Dialect

| Command                              | Description                       |
| ------------------------------------ | --------------------------------- |
| `CREATE TABLE name (col TYPE, ...)`  | Create table with typed columns   |
| `INSERT INTO name VALUES (v1, ...)`  | Insert row                        |
| `SELECT * FROM name [WHERE cond]`    | Select rows (filters with AND)    |
| `DELETE FROM name WHERE cond`        | Delete rows by condition          |
| `CREATE INDEX ON name (col)`         | Create secondary B+tree index     |
| `HELP`                               | Print help                        |
| `CLEAR`                              | Clear screen                      |
| `EXIT`                               | Exit REPL                         |

Types: `INT`, `FLOAT`, `STRING`, `BOOL`, `DATE` (`YYYY-MM-DD`)

---

## Testing

```bash
cd build && ctest --output-on-failure
```

| Suite           | Tests | Coverage                                      |
| --------------- | ----: | --------------------------------------------- |
| `test_value`    |    55 | Value ops, type safety, float/int/string edges |
| `test_bptree`   |    43 | Insert/split/delete/range, Float/Date keys     |
| `test_hash`     |    30 | Point lookup, collision chaining, Bucket edges |
| `test_table`    |    35 | CRUD, NE/GE/LE scan, index, hole reuse         |
| `test_database` |    25 | Multi-table, create/drop lifecycle             |
| `test_parser`   |    44 | All statement types, tokenizer robustness      |
| **Total**       | **232** | 6 suites, 100% pass rate                    |

---

## License

MIT License. Free for use, study, and modification.