Skip to content

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

37 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Testudo

A small embedded database engine, written from scratch in Java, to understand how real databases work under the hood.

What is this?

Testudo is a learning project: an embedded database engine — the same category of software as SQLite or an in-process MySQL — implemented from first principles rather than wrapping an existing engine. It's not intended to replace a production database; it exists to make a database's internals concrete and inspectable, end to end.

It implements its own:

  • B+Tree indexing — the same structure used internally by MySQL's InnoDB and PostgreSQL
  • Clustered + secondary indexes — secondary indexes resolve through the cluster key rather than storing a direct disk pointer, exactly like InnoDB
  • Page-based disk storage, with tombstoned deletes and free-space reuse
  • A schema layer driven by Java annotations (@Collection, @Field, @Index)
  • A query engine — comparison conditions, AND/OR composition, sorted iteration
  • A full CRUD API with per-collection concurrency control and constraint verification (uniqueness, not-null, autoincrement)

Features

  • Two interchangeable on-disk index storage strategies (Compact vs. Organized), swappable via configuration
  • LRU-cached index reads via a transparent decorator — no changes needed in calling code
  • Bitmap-backed indexes for low-cardinality fields, alongside standard B+Tree indexes for everything else
  • Nullable field support that doesn't break index ordering
  • Auto-incrementing primary keys
  • One EngineConfig object controls every tunable: B+Tree degree, page size, cache size, storage strategy, and more

Quick example

@Collection(id = 1, name = "users")
class User {
    @Field(id = 1)
    @Index(primary = true, autoIncrement = true)
    private Integer id;

    @Field(id = 2)
    @Index(unique = true)
    private String email;
}

DatabaseContext context = new DatabaseContextConfigurator() {
    @Override
    public Scheme scheme() {
        Scheme.Collection users = new ModelToCollectionConverter(User.class).toCollection();
        return Scheme.builder().collections(List.of(users)).build();
    }
}.databaseContext();

CollectionOperation userOps = context.getOperation("users");
userOps.execute(new User(null, "rohit@example.com")); // id is assigned automatically

Requirements

  • Java 21
  • Maven

Build & test

mvn test

Compiles the project and runs the full JUnit 5 suite.

Project layout

src/main/java/.../
  context/     engine configuration + top-level wiring (DatabaseContext)
  scheme/      schema model + annotations (@Collection, @Field, @Index)
  index/       index manager interfaces, decorators, B+Tree algorithms
  storage/     file pooling, page-based storage, on-disk index layouts
  serialization/  object <-> byte conversion
  operation/   CRUD operations + the query engine
src/test/java/...   JUnit 5 test suite, mirroring the structure above

Status

This is an actively-evolving practice project, not a finished product. Known gaps — no query support on unindexed fields, no transactions, and a couple of specific, identified issues around cluster-index typing and multi-collection storage locking — are documented in full, along with the reasoning behind every design choice, in DOCUMENTATION.md. That file also includes a from-scratch explanation of every concept for readers new to Java, and an interview-question bank based on this project.

License

MIT — see LICENSE.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages