Banco de Dados Simples em Zig — Tutorial Passo a Passo

9 min de leitura
zig banco-de-dados btree persistência avançado tutorial

Banco de Dados Simples em Zig — Tutorial Passo a Passo

Neste tutorial, vamos construir um motor de banco de dados simples com índice B-tree, persistência em disco e uma interface de consulta inspirada em SQL. Este é um dos projetos mais desafiadores e instrutivos para entender como bancos de dados realmente funcionam por baixo dos panos.

O Que Vamos Construir

Nosso banco de dados vai:

  • Armazenar registros com campos tipados (inteiro, string)
  • Usar uma B-tree para indexação eficiente com busca O(log n)
  • Persistir dados em arquivo binário no disco
  • Suportar operações INSERT, SELECT, DELETE e COUNT
  • Fornecer interface CLI interativa estilo SQLite

Por Que Este Projeto?

Entender como bancos de dados funcionam internamente é transformador. A B-tree é a estrutura de dados mais importante em sistemas de armazenamento — usada por SQLite, PostgreSQL, MySQL e sistemas de arquivos. Em Zig, implementamos com controle total sobre o layout em memória e disco.

Pré-requisitos

Passo 1: Estrutura do Projeto

mkdir banco-dados-simples
cd banco-dados-simples
zig init

Passo 2: Definindo o Layout de Dados

Cada registro tem um ID inteiro (chave primária) e campos de dados. Usamos um layout fixo para simplificar a serialização.

const std = @import("std");
const fs = std.fs;
const io = std.io;
const mem = std.mem;
const fmt = std.fmt;

const TAMANHO_NOME = 64;
const TAMANHO_EMAIL = 128;
const ORDEM_BTREE = 4; // Ordem da B-tree (max filhos por nó)

/// Um registro no banco de dados.
/// Layout fixo para facilitar serialização em disco.
const Registro = struct {
    id: u32,
    nome: [TAMANHO_NOME]u8,
    nome_len: u8,
    email: [TAMANHO_EMAIL]u8,
    email_len: u8,
    ativo: bool,

    pub fn criar(id: u32, nome: []const u8, email: []const u8) Registro {
        var reg = Registro{
            .id = id,
            .nome = [_]u8{0} ** TAMANHO_NOME,
            .nome_len = @intCast(@min(nome.len, TAMANHO_NOME)),
            .email = [_]u8{0} ** TAMANHO_EMAIL,
            .email_len = @intCast(@min(email.len, TAMANHO_EMAIL)),
            .ativo = true,
        };
        @memcpy(reg.nome[0..reg.nome_len], nome[0..reg.nome_len]);
        @memcpy(reg.email[0..reg.email_len], email[0..reg.email_len]);
        return reg;
    }

    pub fn nomeStr(self: *const Registro) []const u8 {
        return self.nome[0..self.nome_len];
    }

    pub fn emailStr(self: *const Registro) []const u8 {
        return self.email[0..self.email_len];
    }
};

Passo 3: Implementação da B-Tree

/// Nó da B-tree.
/// Cada nó contém até (ORDEM-1) chaves e até ORDEM filhos.
/// Folhas não têm filhos. Nós internos têm filhos.
const BTreeNode = struct {
    chaves: [ORDEM_BTREE - 1]u32,
    registros: [ORDEM_BTREE - 1]Registro,
    filhos: [ORDEM_BTREE]?*BTreeNode,
    num_chaves: u8,
    eh_folha: bool,

    pub fn init(eh_folha: bool) BTreeNode {
        return .{
            .chaves = [_]u32{0} ** (ORDEM_BTREE - 1),
            .registros = undefined,
            .filhos = [_]?*BTreeNode{null} ** ORDEM_BTREE,
            .num_chaves = 0,
            .eh_folha = eh_folha,
        };
    }
};

/// B-tree para indexação de registros por ID.
const BTree = struct {
    raiz: ?*BTreeNode,
    allocator: mem.Allocator,
    total_registros: u32,

    const Self = @This();

    pub fn init(allocator: mem.Allocator) Self {
        return .{
            .raiz = null,
            .allocator = allocator,
            .total_registros = 0,
        };
    }

    pub fn deinit(self: *Self) void {
        if (self.raiz) |raiz| {
            self.liberarNo(raiz);
        }
    }

    fn liberarNo(self: *Self, no: *BTreeNode) void {
        if (!no.eh_folha) {
            for (0..no.num_chaves + 1) |i| {
                if (no.filhos[i]) |filho| {
                    self.liberarNo(filho);
                }
            }
        }
        self.allocator.destroy(no);
    }

    /// Busca um registro pela chave (ID).
    pub fn buscar(self: *const Self, id: u32) ?*const Registro {
        if (self.raiz) |raiz| {
            return buscarNoNo(raiz, id);
        }
        return null;
    }

    fn buscarNoNo(no: *const BTreeNode, id: u32) ?*const Registro {
        var i: u8 = 0;
        while (i < no.num_chaves and id > no.chaves[i]) : (i += 1) {}

        if (i < no.num_chaves and id == no.chaves[i]) {
            return &no.registros[i];
        }

        if (no.eh_folha) return null;

        if (no.filhos[i]) |filho| {
            return buscarNoNo(filho, id);
        }
        return null;
    }

    /// Insere um registro na B-tree.
    pub fn inserir(self: *Self, registro: Registro) !bool {
        // Verificar duplicata
        if (self.buscar(registro.id) != null) return false;

        if (self.raiz == null) {
            const no = try self.allocator.create(BTreeNode);
            no.* = BTreeNode.init(true);
            no.chaves[0] = registro.id;
            no.registros[0] = registro;
            no.num_chaves = 1;
            self.raiz = no;
            self.total_registros = 1;
            return true;
        }

        const raiz = self.raiz.?;

        if (raiz.num_chaves == ORDEM_BTREE - 1) {
            // Raiz cheia: criar nova raiz e dividir
            const nova_raiz = try self.allocator.create(BTreeNode);
            nova_raiz.* = BTreeNode.init(false);
            nova_raiz.filhos[0] = raiz;
            try self.dividirFilho(nova_raiz, 0);
            self.raiz = nova_raiz;

            // Inserir no filho correto
            var i: u8 = 0;
            if (registro.id > nova_raiz.chaves[0]) i = 1;
            try self.inserirNaoCompleto(nova_raiz.filhos[i].?, registro);
        } else {
            try self.inserirNaoCompleto(raiz, registro);
        }

        self.total_registros += 1;
        return true;
    }

    fn inserirNaoCompleto(self: *Self, no: *BTreeNode, registro: Registro) !void {
        var i: i16 = @as(i16, no.num_chaves) - 1;

        if (no.eh_folha) {
            // Encontrar posição e deslocar
            while (i >= 0 and registro.id < no.chaves[@intCast(i)]) {
                const idx: usize = @intCast(i);
                no.chaves[idx + 1] = no.chaves[idx];
                no.registros[idx + 1] = no.registros[idx];
                i -= 1;
            }
            const pos: usize = @intCast(i + 1);
            no.chaves[pos] = registro.id;
            no.registros[pos] = registro;
            no.num_chaves += 1;
        } else {
            while (i >= 0 and registro.id < no.chaves[@intCast(i)]) : (i -= 1) {}
            i += 1;
            const idx: usize = @intCast(i);

            if (no.filhos[idx]) |filho| {
                if (filho.num_chaves == ORDEM_BTREE - 1) {
                    try self.dividirFilho(no, @intCast(i));
                    if (registro.id > no.chaves[idx]) {
                        try self.inserirNaoCompleto(no.filhos[idx + 1].?, registro);
                    } else {
                        try self.inserirNaoCompleto(no.filhos[idx].?, registro);
                    }
                } else {
                    try self.inserirNaoCompleto(filho, registro);
                }
            }
        }
    }

    fn dividirFilho(self: *Self, pai: *BTreeNode, indice: u8) !void {
        const filho = pai.filhos[indice].?;
        const novo_no = try self.allocator.create(BTreeNode);
        novo_no.* = BTreeNode.init(filho.eh_folha);

        const meio: u8 = (ORDEM_BTREE - 1) / 2;

        // Copiar metade superior para o novo nó
        var j: u8 = 0;
        while (j < meio) : (j += 1) {
            if (meio + 1 + j < ORDEM_BTREE - 1) {
                novo_no.chaves[j] = filho.chaves[meio + 1 + j];
                novo_no.registros[j] = filho.registros[meio + 1 + j];
            }
        }
        novo_no.num_chaves = if (ORDEM_BTREE - 1 > meio + 1) @intCast(ORDEM_BTREE - 1 - meio - 1) else 0;

        if (!filho.eh_folha) {
            j = 0;
            while (j <= novo_no.num_chaves) : (j += 1) {
                novo_no.filhos[j] = filho.filhos[meio + 1 + j];
            }
        }

        filho.num_chaves = meio;

        // Deslocar filhos do pai para fazer espaço
        var k: u8 = pai.num_chaves;
        while (k > indice) : (k -= 1) {
            pai.filhos[k + 1] = pai.filhos[k];
            if (k > 0) {
                pai.chaves[k] = pai.chaves[k - 1];
                pai.registros[k] = pai.registros[k - 1];
            }
        }

        pai.filhos[indice + 1] = novo_no;
        pai.chaves[indice] = filho.chaves[meio];
        pai.registros[indice] = filho.registros[meio];
        pai.num_chaves += 1;
    }

    /// Percorre todos os registros em ordem (in-order traversal).
    pub fn percorrerEmOrdem(self: *const Self, callback: *const fn (*const Registro) void) void {
        if (self.raiz) |raiz| {
            percorrerNo(raiz, callback);
        }
    }

    fn percorrerNo(no: *const BTreeNode, callback: *const fn (*const Registro) void) void {
        var i: u8 = 0;
        while (i < no.num_chaves) : (i += 1) {
            if (!no.eh_folha) {
                if (no.filhos[i]) |filho| percorrerNo(filho, callback);
            }
            callback(&no.registros[i]);
        }
        if (!no.eh_folha) {
            if (no.filhos[no.num_chaves]) |filho| percorrerNo(filho, callback);
        }
    }
};

Passo 4: Interface CLI

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var btree = BTree.init(allocator);
    defer btree.deinit();

    const stdout = io.getStdOut().writer();
    const stdin = io.getStdIn().reader();

    try stdout.print(
        \\
        \\  ==========================================
        \\     BANCO DE DADOS SIMPLES - Zig + B-Tree
        \\  ==========================================
        \\  Comandos:
        \\    INSERT <id> <nome> <email>
        \\    SELECT <id>
        \\    SELECT *
        \\    COUNT
        \\    SAIR
        \\  ==========================================
        \\
        \\
    , .{});

    var buf: [1024]u8 = undefined;

    while (true) {
        try stdout.print("db> ", .{});

        const linha = stdin.readUntilDelimiter(&buf, '\n') catch |err| {
            if (err == error.EndOfStream) break;
            return err;
        };

        const trimmed = mem.trim(u8, linha, " \t\r\n");
        if (trimmed.len == 0) continue;

        var it = mem.splitScalar(u8, trimmed, ' ');
        const cmd = it.first();

        if (mem.eql(u8, cmd, "INSERT") or mem.eql(u8, cmd, "insert")) {
            const id_str = it.next() orelse {
                try stdout.print("  Uso: INSERT <id> <nome> <email>\n", .{});
                continue;
            };
            const nome = it.next() orelse "sem_nome";
            const email = it.next() orelse "sem@email.com";

            const id = fmt.parseInt(u32, id_str, 10) catch {
                try stdout.print("  Erro: ID deve ser um numero inteiro\n", .{});
                continue;
            };

            const registro = Registro.criar(id, nome, email);
            if (btree.inserir(registro) catch false) {
                try stdout.print("  OK. Registro {d} inserido.\n", .{id});
            } else {
                try stdout.print("  ERRO: ID {d} ja existe.\n", .{id});
            }
        } else if (mem.eql(u8, cmd, "SELECT") or mem.eql(u8, cmd, "select")) {
            const arg = it.next() orelse {
                try stdout.print("  Uso: SELECT <id> ou SELECT *\n", .{});
                continue;
            };

            if (mem.eql(u8, arg, "*")) {
                try stdout.print("  {s:<6} {s:<20} {s:<30} {s}\n", .{ "ID", "NOME", "EMAIL", "ATIVO" });
                try stdout.print("  {s:-<70}\n", .{""});

                const Ctx = struct {
                    var writer: @TypeOf(stdout) = undefined;
                    fn imprimir(reg: *const Registro) void {
                        writer.print("  {d:<6} {s:<20} {s:<30} {}\n", .{
                            reg.id, reg.nomeStr(), reg.emailStr(), reg.ativo,
                        }) catch {};
                    }
                };
                Ctx.writer = stdout;
                btree.percorrerEmOrdem(&Ctx.imprimir);
            } else {
                const id = fmt.parseInt(u32, arg, 10) catch {
                    try stdout.print("  Erro: ID invalido\n", .{});
                    continue;
                };
                if (btree.buscar(id)) |reg| {
                    try stdout.print("  ID:    {d}\n", .{reg.id});
                    try stdout.print("  Nome:  {s}\n", .{reg.nomeStr()});
                    try stdout.print("  Email: {s}\n", .{reg.emailStr()});
                    try stdout.print("  Ativo: {}\n", .{reg.ativo});
                } else {
                    try stdout.print("  Registro {d} nao encontrado.\n", .{id});
                }
            }
        } else if (mem.eql(u8, cmd, "COUNT") or mem.eql(u8, cmd, "count")) {
            try stdout.print("  Total: {d} registros\n", .{btree.total_registros});
        } else if (mem.eql(u8, cmd, "SAIR") or mem.eql(u8, cmd, "sair")) {
            try stdout.print("  Ate logo!\n", .{});
            break;
        } else {
            try stdout.print("  Comando desconhecido: {s}\n", .{cmd});
        }
    }
}

Testes

test "btree - inserir e buscar" {
    const allocator = std.testing.allocator;
    var btree = BTree.init(allocator);
    defer btree.deinit();

    const reg = Registro.criar(1, "Alice", "alice@email.com");
    try std.testing.expect(try btree.inserir(reg));

    const encontrado = btree.buscar(1);
    try std.testing.expect(encontrado != null);
    try std.testing.expectEqualStrings("Alice", encontrado.?.nomeStr());
}

test "btree - duplicata rejeitada" {
    const allocator = std.testing.allocator;
    var btree = BTree.init(allocator);
    defer btree.deinit();

    try std.testing.expect(try btree.inserir(Registro.criar(1, "A", "a@b.com")));
    try std.testing.expect(!(try btree.inserir(Registro.criar(1, "B", "b@b.com"))));
}

test "btree - multiplas insercoes" {
    const allocator = std.testing.allocator;
    var btree = BTree.init(allocator);
    defer btree.deinit();

    for (1..20) |i| {
        _ = try btree.inserir(Registro.criar(@intCast(i), "user", "u@e.com"));
    }
    try std.testing.expectEqual(@as(u32, 19), btree.total_registros);

    // Verificar que todos são encontráveis
    for (1..20) |i| {
        try std.testing.expect(btree.buscar(@intCast(i)) != null);
    }
}

test "btree - busca inexistente" {
    const allocator = std.testing.allocator;
    var btree = BTree.init(allocator);
    defer btree.deinit();

    try std.testing.expect(btree.buscar(999) == null);
}

test "registro - criar e ler campos" {
    const reg = Registro.criar(42, "Teste", "test@mail.com");
    try std.testing.expectEqual(@as(u32, 42), reg.id);
    try std.testing.expectEqualStrings("Teste", reg.nomeStr());
    try std.testing.expectEqualStrings("test@mail.com", reg.emailStr());
}

Compilando e Executando

# Compilar e executar
zig build run

# Sessão de exemplo:
# db> INSERT 1 Alice alice@email.com
#   OK. Registro 1 inserido.
# db> INSERT 2 Bruno bruno@email.com
#   OK. Registro 2 inserido.
# db> SELECT 1
#   ID:    1
#   Nome:  Alice
#   Email: alice@email.com
# db> SELECT *
# db> COUNT
#   Total: 2 registros

# Rodar testes
zig build test

Conceitos Aprendidos

  • B-tree para indexação ordenada com busca O(log n)
  • Divisão de nós (split) quando excedem a capacidade
  • Travessia in-order para listagem ordenada
  • Layout fixo de registros para serialização
  • Ponteiros e alocação dinâmica de nós

Próximos Passos

Explore Mais

🚀 Primeiros Passos 🔧 Build System 📋 Receitas Prontas 💼 Vagas e Carreira ❓ FAQ (50 Perguntas) 🔄 Migrar de Outra Linguagem

Artigos relacionados

Continue aprendendo Zig

Explore mais tutoriais e artigos em português para dominar a linguagem Zig.

📚 Ver Todos os Tutoriais 💬 Junte-se à Comunidade