file-based nosql db

BTree.ts

class BTreeNode {
    keys: number[];
    children: BTreeNode[];
    numKeys: number;
    constructor(private minDegree: number, public isLeaf: boolean) {
        this.keys = new Array(2 * this.minDegree - 1);
        this.children = new Array(2 * this.minDegree);
        this.numKeys = 0;
    }
    findKey(key: number): number {
        let idx = 0;
        while (idx < this.numKeys && this.keys[idx] < key) {
            idx++;
        }
        return idx;
    }
    splitChild(idx: number, node: BTreeNode) {
        let newNode = new BTreeNode(node.minDegree, node.isLeaf);
        newNode.numKeys = this.minDegree - 1;
        for (let j = 0; j < this.minDegree - 1; j++) {
            newNode.keys[j] = node.keys[j + this.minDegree];
        }
        if (!node.isLeaf) {
            for (let j = 0; j < this.minDegree; j++) {
                newNode.children[j] = node.children[j + this.minDegree];
            }
        }
        node.numKeys = this.minDegree - 1;
        for (let j = this.numKeys; j > idx; j--) {
            this.children[j + 1] = this.children[j];
        }
        this.children[idx + 1] = newNode;
        for (let j = this.numKeys - 1; j > idx - 1; j--) {
            this.keys[j + 1] = this.keys[j];
        }
        this.keys[idx] = node.keys[this.minDegree - 1];
        this.numKeys++;
    }
    remove(key: number): void {
        let idx = this.findKey(key);
        if (idx < this.numKeys && this.keys[idx] == key) {
            if (this.isLeaf) {
                this.removeFromLeaf(idx);
                return;
            }
            this.removeFromNonLeaf(idx);
            return;
        }
        if (this.isLeaf) {
            // could maybe throw an error here or something
            return;
        }
        let flag = ((idx == this.numKeys) ? true : false);
        if (this.children[idx].numKeys < this.minDegree) {
            this.fill(idx);
        }
        if (flag && idx > this.numKeys) {
            this.children[idx - 1].remove(key);
            return;
        }
        this.children[idx].remove(key);
    }
    removeFromLeaf(idx: number): void {
        for (let i = idx + 1; i < this.numKeys; i++) {
            this.keys[i - 1] = this.keys[i];
        }
        this.numKeys--;
    }
    removeFromNonLeaf(idx: number): void {
        let key = this.keys[idx];
        if (this.children[idx].numKeys >= this.minDegree) {
            let pred = this.getPredecessor(idx);
            this.keys[idx] = pred;
            this.children[idx].remove(pred);
            return;
        }
        if (this.children[idx + 1].numKeys >= this.minDegree) {
            let succ = this.getSuccessor(idx);
            this.keys[idx] = succ;
            this.children[idx + 1].remove(succ);
            return;
        }
        this.merge(idx);
        this.children[idx].remove(key);
    }
    getPredecessor(idx: number): number {
        let cur = this.children[idx];
        while (!cur.isLeaf) {
            cur = cur.children[cur.numKeys];
        }
        return cur.keys[cur.numKeys - 1];
    }
    getSuccessor(idx: number): number {
        let cur = this.children[idx + 1];
        while (!cur.isLeaf) {
            cur = cur.children[0];
        }
        return cur.keys[0];
    }
    fill(idx: number): void {
        if (idx != 0 && this.children[idx - 1].numKeys >= this.minDegree) {
            this.borrowFromPrev(idx);
            return;
        }
        if (idx != this.numKeys && this.children[idx + 1].numKeys >= this.minDegree) {
            this.borrowFromNext(idx);
            return;
        }
        if (idx != this.numKeys) {
            this.merge(idx);
            return;
        }
        this.merge(idx - 1);
    }
    insertNonFull(key: number) {
        let i = this.numKeys - 1;
        if (this.isLeaf) {
            while (i >= 0 && this.keys[i] > key) {
                this.keys[i + 1] = this.keys[i];
                i--;
            }
            this.keys[i + 1] = key;
            this.numKeys++;
            return;
        }
        while (i >= 0 && this.keys[i] > key) {
            i--;
        }
        if (this.children[i + 1].numKeys === 2 * this.minDegree - 1) {
            this.splitChild(i + 1, this.children[i + 1]);
            if (this.keys[i + 1] < key) {
                i++;
            }
        }
        this.children[i + 1].insertNonFull(key);
    }
    borrowFromPrev(idx: number): void {
        let child = this.children[idx];
        let sibling = this.children[idx - 1];
        for (let i = child.numKeys - 1; i >= 0; --i) {
            child.keys[i + 1] = child.keys[i];
        }
        if (!child.isLeaf) {
            for (let i = child.numKeys; i >= 0; --i) {
                child.children[i + 1] = child.children[i];
            }
        }
        child.keys[0] = this.keys[idx - 1];
        if (!child.isLeaf) {
            child.children[0] = sibling.children[sibling.numKeys];
        }
        this.keys[idx - 1] = sibling.keys[sibling.numKeys - 1];
        child.numKeys += 1;
        sibling.numKeys -= 1;
    }
    borrowFromNext(idx: number): void {
        let child = this.children[idx];
        let sibling = this.children[idx + 1];
        child.keys[(child.numKeys)] = this.keys[idx];
        if (!child.isLeaf) {
            child.children[(child.numKeys) + 1] = sibling.children[0];
        }
        this.keys[idx] = sibling.keys[0];
        for (let i = 1; i < sibling.numKeys; i++) {
            sibling.keys[i - 1] = sibling.keys[i];
        }
        if (!sibling.isLeaf) {
            for (let i = 1; i <= sibling.numKeys; i++) {
                sibling.children[i - 1] = sibling.children[i];
            }
        }
        child.numKeys += 1;
        sibling.numKeys -= 1;
    }
    merge(idx: number): void {
        let child = this.children[idx];
        let sibling = this.children[idx + 1];
        child.keys[this.minDegree - 1] = this.keys[idx];
        for (let i = 0; i < sibling.numKeys; i++) {
            child.keys[i + this.minDegree] = sibling.keys[i];
        }
        if (!child.isLeaf) {
            for (let i = 0; i <= sibling.numKeys; i++) {
                child.children[i + this.minDegree] = sibling.children[i];
            }
        }
        for (let i = idx + 1; i < this.numKeys; i++) {
            this.keys[i - 1] = this.keys[i];
        }
        for (let i = idx + 2; i <= this.numKeys; i++) {
            this.children[i - 1] = this.children[i];
        }
        child.numKeys += sibling.numKeys + 1;
        this.numKeys--;
    }
    traverse(logger: Logger = console): void {
        let i;
        for (i = 0; i < this.numKeys; i++) {
            if (this.isLeaf == false) {
                this.children[i].traverse(logger);
            }
            logger.log(this.keys[i]);
        }
        if (this.isLeaf == false) {
            this.children[i].traverse(logger);
        }
    }
    search(k: number): BTreeNode | null {
        let i = 0;
        while (i < this.numKeys && k > this.keys[i]) {
            i++;
        }
        if (this.keys[i] == k) {
            return this;
        }
        if (this.isLeaf == true) {
            return null;
        }
        return this.children[i].search(k);
    }

    map<U>(f: (x: number) => U): U[] {
        let res: U[] = [];
        for (let i = 0; i < this.numKeys; i++) {
            if (this.isLeaf == false)
                res = res.concat(this.children[i].map(f));
            res.push(f(this.keys[i]));
        }
        if (this.isLeaf == false)
            res = res.concat(this.children[this.numKeys].map(f));
        return res;
    }

    isBalanced(): boolean {
        let i = 0;
        if (this.isLeaf) {
            return true;
        }
        for (i = 0; i < this.numKeys; i++) {
            if (!this.children[i].isBalanced()) {
                return false;
            }
        }
        if (!this.children[i].isBalanced()) {
            return false;
        }
        return true;
    }
}
export class BTree {
    root: BTreeNode | null;
    constructor(private minDegree: number = 3) {
        this.root = null;
    }

    traverse(logger: Logger = console): void {
        if (this.root != null) {
            this.root.traverse(logger);
        }
    }

    search(k: number): number | null {
        const found = (this.root == null) ? null : this.root.search(k);
        if (found) {
            return k;
        }
        return null;
    }

    insert(k: number): void {
        if (this.root == null) {
            this.root = new BTreeNode(this.minDegree, true);
            this.root.keys[0] = k;
            this.root.numKeys = 1;
            return;
        }

        if (this.root.numKeys == 2 * this.minDegree - 1) {
            let s = new BTreeNode(this.minDegree, false);
            s.children[0] = this.root;
            s.splitChild(0, this.root);
            let i = 0;
            if (s.keys[0] < k) {
                i++;
            }
            s.children[i].insertNonFull(k);
            this.root = s;
            return;
        }

        this.root.insertNonFull(k);
    }

    delete(k: number): void {
        if (!this.root) {
            // could maybe throw an error here or something idk
            return;
        }
        this.root.remove(k);
        if (this.root.numKeys == 0) {
            if (this.root.isLeaf) {
                this.root = null;
            } else {
                this.root = this.root.children[0];
            }
            return;
        }
        return;
    }

    map<U>(f: (x: number) => U): U[] {
        if (!this.root) {
            return [];
        }
        return this.root.map(f);
    }

    isBalanced(): boolean {
        if (!this.root) {
            return true;
        }
        return this.root.isBalanced();
    }
}

interface Logger {
    log: (...x: any[]) => void;
}

nosql.ts

import { promises as fs } from 'fs';
import crypto from 'crypto';
import { Mutex } from 'async-mutex';
import { BTree } from './BTree';

interface Document {
    [key: string]: any;
}

interface Index {
    [key: string]: { [value: string]: BTree };
}

interface Condition {
    $eq?: any;
    $gt?: number;
    $gte?: number;
    $lt?: number;
    $lte?: number;
    $ne?: any;
    $in?: any[];
    $nin?: any[];
}

interface Query {
    [key: string]: any | Condition;
}

export class Collection {
    private path: string;
    private index: Index = {};
    private mutex: Mutex = new Mutex();

    constructor(path: string) {
        this.path = path;
        this.loadIndex();
    }

    private async loadIndex(): Promise<void> {
        try {
            const data = await fs.readFile(`${this.path}/index.json`, 'utf-8');
            this.index = JSON.parse(data);
        } catch (err) {
            if (!this.isFileNotFoundError(err)) {
                throw err;
            }
        }
    }

    private async saveIndex(): Promise<void> {
        await fs.writeFile(`${this.path}/index.json`, JSON.stringify(this.index));
    }

    private updateIndex(id: number, doc: Document): void {
        for (const key in doc) {
            const value = doc[key];
            if (!this.index[key]) {
                this.index[key] = {};
            }
            if (!this.index[key][value]) {
                this.index[key][value] = new BTree();
            }
            this.index[key][value].insert(id);
        }
    }

    private removeFromIndex(id: number, doc: Document): void {
        for (const key in doc) {
            const value = doc[key];
            if (this.index[key] && this.index[key][value]) {
                this.index[key][value].delete(id);
            }
        }
    }

    async create(doc: Document): Promise<number> {
        const release = await this.mutex.acquire();
        try {
            const id = crypto.randomInt(0, 1000000000);
            await fs.writeFile(`${this.path}/${id}.json`, JSON.stringify(doc));
            this.updateIndex(id, doc);
            await this.saveIndex();
            return id;
        } finally {
            release();
        }
    }

    async read(id: number): Promise<Document | null> {
        try {
            const data = await fs.readFile(`${this.path}/${id}.json`, 'utf-8');
            return JSON.parse(data);
        } catch (err) {
            if (this.isFileNotFoundError(err)) {
                return null;
            }
            throw err;
        }
    }

    async update(id: number, doc: Document): Promise<void> {
        const release = await this.mutex.acquire();
        try {
            const oldDoc = await this.read(id);
            if (oldDoc) {
                this.removeFromIndex(id, oldDoc);
            }
            await fs.writeFile(`${this.path}/${id}.json`, JSON.stringify(doc));
            this.updateIndex(id, doc);
            await this.saveIndex();
        } finally {
            release();
        }
    }

    async delete(id: number): Promise<void> {
        const release = await this.mutex.acquire();
        try {
            const doc = await this.read(id);
            if (doc) {
                this.removeFromIndex(id, doc);
            }
            await fs.unlink(`${this.path}/${id}.json`);
            await this.saveIndex();
        } finally {
            release();
        }
    }

    private match(doc: Document, query: Query): boolean {
        for (const key in query) {
            const value = doc[key];
            const condition = query[key];
            if (typeof condition === 'object' && condition !== null) {
                const conditionFalse = (condition.$eq !== undefined && value !== condition.$eq)
                    || (condition.$gt !== undefined && value <= condition.$gt)
                    || (condition.$gte !== undefined && value < condition.$gte)
                    || (condition.$lt !== undefined && value >= condition.$lt)
                    || (condition.$lte !== undefined && value > condition.$lte)
                    || (condition.$ne !== undefined && value === condition.$ne)
                    || (condition.$in !== undefined && !condition.$in.includes(value))
                    || (condition.$nin !== undefined && condition.$nin.includes(value));

                if (conditionFalse) {
                    return false;
                }
            } else {
                if (value !== condition) {
                    return false;
                }
            }
        }
        return true;
    }

    async query(query: Query): Promise<Document[]> {
        const ids = new BTree();
        for (const key in query) {
            const condition = query[key];
            if (typeof condition === 'object' && condition !== null) {
                for (const op in condition) {
                    switch (op) {
                        case '$eq':
                            const eqIds = this.index[key] && this.index[key][condition[op]];
                            if (eqIds) {
                                for (const id of eqIds.map(x=>x)) {
                                    ids.insert(id);
                                }
                            }
                            break;
                        case '$gt':
                        case '$gte':
                        case '$lt':
                        case '$lte':
                            for (const value in this.index[key]) {
                                if ((op === '$gt' && value > condition[op]) ||
                                    (op === '$gte' && value >= condition[op]) ||
                                    (op === '$lt' && value < condition[op]) ||
                                    (op === '$lte' && value <= condition[op])) {
                                    for (const id of this.index[key][value].map(x=>x)) {
                                        ids.insert(id);
                                    }
                                }
                            }
                            break;
                        case '$ne':
                            for (const value in this.index[key]) {
                                if (value !== condition[op]) {
                                    for (const id of this.index[key][value].map(x=>x)) {
                                        ids.insert(id);
                                    }
                                }
                            }
                            break;
                        case '$in':
                        case '$nin':
                            for (const value in this.index[key]) {
                                if ((op === '$in' && condition[op].includes(value)) ||
                                    (op === '$nin' && !condition[op].includes(value))) {
                                    for (const id of this.index[key][value].map(x=>x)) {
                                        ids.insert(id);
                                    }
                                }
                            }
                            break;
                    }
                }
            } else {
                const eqIds = this.index[key] && this.index[key][condition];
                if (eqIds) {
                    for (const id of eqIds.map(x=>x)) {
                        ids.insert(id);
                    }
                }
            }
        }
        const docs = await Promise.all(ids.map(id => this.read(id)));
        return docs.filter(doc => doc !== null && this.match(doc, query)) as Document[];
    }

    async backup(): Promise<void> {
        await fs.copyFile(`${this.path}/index.json`, `${this.path}/index.json.bak`);
    }

    async restore(): Promise<void> {
        await fs.copyFile(`${this.path}/index.json.bak`, `${this.path}/index.json`);
        await this.loadIndex();
    }

    private isFileNotFoundError(err: unknown): boolean {
        if (typeof err !== 'object' || err === null || !('code' in err)) {
            return false;
        }
        return err.code === 'ENOENT';
    }
}