TinyDB

Hash & B+ Tree Indexing on Open Source TinyDB ( Associated with USC Advanced Data Stores - Project II)

TinyDB with User-Defined Indexing

📌 Overview

This project extends TinyDB, a lightweight document-oriented NoSQL database written in Python, with user-defined indexing.

By default, TinyDB executes all queries using a full scan (O(N)), which limits scalability. Our solution introduces Hash Indexing and B+ Tree Indexing, allowing users to define which fields to index and enabling much faster exact-match and range queries.

---

Features

• 🔹 User-defined indexing inspired by Redis JSON Indexing
• 🔹 Support for nested fields using JSONPath syntax
• 🔹 Hash Indexing for exact-match queries → O(1) lookups
• 🔹 B+ Tree Indexing for range queries → O(log n) lookups
• 🔹 Indexes stored on disk for persistence
• 🔹 Automatic fallback to full scan if no index exists

---

🚀 Getting Started

Prerequisites

• Python 3.8+
• TinyDB

Installation

bash git clone https://github.com/yourusername/tinydb-indexing.git cd tinydb-indexing pip install -r requirements.txt

Creating Indexes

Create exact match index on a nested field

db.create_index("$.user.a", "a", "TEXT")

Create numeric range index

db.create_index("$.age", "age", "NUMERIC")

Example Document

{ "user": { "a": "abc" }, "id": 1 } { "user": { "a": "def" }, "id": 2 } { "age": 24, "name": "Frank" } { "sub": "ads", "rollno": 17 } { "age": 23, "name": "Roshni" } { "age": 24, "name": "Neelam" }

Queries

Exact Match Query (Hash Index)

db.search(('name', 'Roshni')) # O(1) lookup

Range Query (B+ Tree Index)

db.search({'age': (20, 30)}) # O(log n + k)