the ugly org - hacemos una db 2 - relational

desu

Hello,

Bienvenidos a una nueva serie que constara de dos partes:


Bienvenidos a la parte dos. Importante, esta es la parte 2 porque es necesario haber hecho la parte 1.

Me voy a basar en el material de Build Your Own Database From Scratch in Go pero lo haremos en Rust. No haremos todo exactamente igual que en el material de referencia. Como en el anterior parte implementamos un paper, he pensado que estaría bien seguir un recurso mas accesible para los noveles.

Y si todo va bien, quizás quizás, hay una parte 3! Que si alguien sabe algo de bases de datos, ya debería intuir que va a ser.

Como siempre, el lector es invitado a comentar lo que quiera.

1
desu

Voy a poner aqui el README, y de momento esto sera el objetivo a lograr:
https://github.com/vrnvu/branchdb


branchdb

BranchDB is a Rust implementation of a database engine focusing on B+Tree storage with SQL-like capabilities. Here's the summary in 10 lines:

  1. Core Idea: B+Tree-based storage engine with durability guarantees
  2. Indexing: B+Tree for efficient range queries and data organization
  3. Data Layout: Copy-on-write B+Tree for ACID compliance
  4. Storage: Append-only file structure with crash recovery
  5. Concurrency: Support for concurrent transactions
  6. Query Engine: SQL-like query language implementation
  7. Secondary Indexes: Multiple index support for query optimization
  8. Data Integrity: Crash recovery and atomic operations
  9. Tables: Relational model built on top of key-value store
  10. Design Principles: Simplicity, durability, and SQL compatibility

Project

This implementation provides:

  • A Rust library for embedding in other projects
  • Core features including:
    • B+Tree-based storage engine
    • Copy-on-write for ACID transactions
    • SQL-like query language
    • Secondary indexes support
    • Concurrent transaction processing
    • Crash recovery mechanisms

Implementation Details

Storage Engine

  • B+Tree for primary data organization
  • Copy-on-write for transaction isolation
  • Append-only log for durability
  • Free list management for space reuse

Query Processing

  • SQL parser and lexer
  • Query optimizer
  • Transaction manager
  • Concurrent execution engine

Durability Guarantees

  • ACID compliance through copy-on-write
  • Crash recovery via WAL (Write-Ahead Logging)
  • Atomic transactions

Limitations

  • Single-node operations only
  • In-memory B+Tree structure
  • Limited SQL feature set

Comparison with other databases

TODO

FeatureBranchDBSQLitePostgreSQL
ArchitectureB+TreeB-TreeMVCC
ConcurrencyYes (transactions)LimitedFull
StorageAppend-onlyPagedHeap files
Query LanguageSQL-likeSQLSQL
IndexesB+TreeB-TreeMultiple types
TransactionsACIDACIDACID
RecoveryWALWALWAL + REDO
LanguageRustCC
1

Usuarios habituales

  • desu