Storage and retrieval

#!/bin/bash

db_set() {
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

# Python implementation
class SimpleDB:
    def __init__(self, filename='database.txt'):
        self.filename = filename

    def set(self, key, value):
        """O(1) - Fast writes"""
        with open(self.filename, 'a') as f:
            f.write(f"{key},{value}\n")

    def get(self, key):
        """O(n) - Slow reads"""
        result = None
        with open(self.filename, 'r') as f:
            for line in f:
                if line.startswith(f"{key},"):
                    result = line.split(',', 1)[1].strip()
        return result

# Usage
db = SimpleDB()
db.set('user:1', 'Alice')
db.set('user:2', 'Bob')
db.set('user:1', 'Alice Updated')  # Update by appending

print(db.get('user:1'))  # Returns 'Alice Updated'

class HashIndexDB:
    def __init__(self, filename='data.db'):
        self.filename = filename
        self.index = {}  # key -> byte offset
        self.file = open(filename, 'a+b')
        self._build_index()

    def _build_index(self):
        """Build index by scanning entire file"""
        self.file.seek(0)
        offset = 0

        while True:
            line = self.file.readline()
            if not line:
                break

            key = line.split(b',', 1)[0].decode()
            self.index[key] = offset  # Latest offset for this key
            offset = self.file.tell()

    def set(self, key, value):
        """Write to end of file and update index"""
        data = f"{key},{value}\n".encode()
        offset = self.file.tell()

        self.file.write(data)
        self.file.flush()

        self.index[key] = offset  # Update index

    def get(self, key):
        """Use index to find data quickly"""
        if key not in self.index:
            return None

        offset = self.index[key]
        self.file.seek(offset)
        line = self.file.readline().decode()

        return line.split(',', 1)[1].strip()

# Usage
db = HashIndexDB()
db.set('temperature:2024-01-15', '72')
db.set('temperature:2024-01-16', '68')
print(db.get('temperature:2024-01-15'))  # Fast lookup: O(1)

class LSMTree:
    def __init__(self):
        self.memtable = {}  # In-memory sorted tree (simplified as dict)
        self.sstables = []  # List of SSTable files on disk
        self.memtable_size = 0
        self.memtable_threshold = 1024 * 1024  # 1 MB

    def write(self, key, value):
        """Write to memtable"""
        # 1. Write to memtable
        self.memtable[key] = value
        self.memtable_size += len(key) + len(value)

        # 2. If memtable is full, flush to disk
        if self.memtable_size > self.memtable_threshold:
            self._flush_memtable()

    def _flush_memtable(self):
        """Write memtable to disk as SSTable"""
        # 1. Sort keys
        sorted_items = sorted(self.memtable.items())

        # 2. Write to new SSTable file
        sstable_file = f"sstable_{len(self.sstables)}.db"
        with open(sstable_file, 'w') as f:
            for key, value in sorted_items:
                f.write(f"{key},{value}\n")

        # 3. Add to list of SSTables
        self.sstables.append(sstable_file)

        # 4. Clear memtable
        self.memtable = {}
        self.memtable_size = 0

    def read(self, key):
        """Read from memtable and SSTables"""
        # 1. Check memtable first (most recent data)
        if key in self.memtable:
            return self.memtable[key]

        # 2. Check SSTables from newest to oldest
        for sstable_file in reversed(self.sstables):
            value = self._search_sstable(sstable_file, key)
            if value is not None:
                return value

        return None

    def _search_sstable(self, filename, key):
        """Binary search in sorted SSTable"""
        with open(filename, 'r') as f:
            # Simplified: in reality, use sparse index + binary search
            for line in f:
                k, v = line.strip().split(',', 1)
                if k == key:
                    return v
                if k > key:  # Passed it, not found
                    return None
        return None

class BTreeNode:
    def __init__(self, is_leaf=False):
        self.keys = []
        self.children = []
        self.is_leaf = is_leaf

class BTree:
    def __init__(self, t=3):  # t = minimum degree (min keys = t-1)
        self.root = BTreeNode(is_leaf=True)
        self.t = t

    def search(self, key, node=None):
        """Search for key in B-tree"""
        if node is None:
            node = self.root

        # Find first key >= search key
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        # If found at this node
        if i < len(node.keys) and key == node.keys[i]:
            return True

        # If leaf node, key not found
        if node.is_leaf:
            return False

        # Recurse to appropriate child
        return self.search(key, node.children[i])

# Original column (100 million rows)
city_column = ['SF'] * 30_000_000 + ['NY'] * 40_000_000 + ['LA'] * 30_000_000

# Uncompressed: ~1.2 GB (assuming 12 bytes per string)

# Run-length encoded:
compressed = [
    ('SF', 30_000_000),
    ('NY', 40_000_000),
    ('LA', 30_000_000)
]
# Compressed: ~36 bytes!
# Compression ratio: 33,000,000:1