Implement a SQL Engine's Storage Layer: Create Database, Schema, Table and Row CRUD

You are working inside a SQL engine. Earlier stages have already parsed, validated, and optimized each statement. Your job is the last step: the layer that carries out each operation and writes the result to disk. Implement the interfaces this layer exposes for creating a database, a schema, and a table, and for inserting, reading, updating, and deleting rows, so that everything written survives a restart of the process. The round was billed as algorithms and data structures, but the task is this storage layer. SQL parsing, validation, and optimization are out of scope. ### Constraints and Clarifications - Input reaching your layer has already passed validation. You still need to handle errors that depend on stored state, such as creating a table that already exists. - The namespace has three levels: a database contains schemas, and a schema contains tables. ### Clarifying Questions - In what form do row filters reach this layer: a predicate function, a simple column-equals-value condition, or a list of row identifiers chosen by the optimizer? - Which column types must be supported, and can values be NULL? - What durability is required: must a completed write survive a crash immediately, or only a clean shutdown? - Must a statement that changes several rows be atomic? - Can several sessions write at the same time, or is there a single writer? - Are indexes in scope, or may reads scan the table? ### Part 1 — Creating databases, schemas, and tables Implement `create_database`, `create_schema`, and `create_table`, where a table is created with a list of column names and types. Created objects must persist on disk and be visible after a restart. ```hint Where does the catalog live? Decide how the engine records which databases, schemas, tables, and columns exist, and what a crash in the middle of a create could leave behind. ``` #### What This Part Should Cover - An on-disk representation of the three-level namespace and of each table's column definitions - Errors for duplicates and for missing parents - A create operation that a crash cannot leave half-done ### Part 2 — Insert, select, update, and delete Implement `insert`, `select`, `update`, and `delete` on a table, with every change persisted to disk. ```hint How do you find a row again? Decide how a row is identified and laid out on disk, and what an update does when the new version of a row no longer fits where the old one was. ``` #### What This Part Should Cover - A row format and file layout, and how rows are located for update and delete - The persistence path for each operation, and what happens on restart - Time complexity of each operation, and memory use - Type checking against the table's columns ### What a Strong Answer Covers - Clear interface signatures, agreed before coding - A storage design explained at the level of files, records, and identifiers - Crash behavior and durability addressed explicitly - Correct error handling for missing and duplicate objects - Trade-offs between a simple design and a production-grade one ### Follow-up Questions - The process crashes halfway through an update that touches many rows. What does the table look like after a restart, and how would you make the statement all-or-nothing? - Queries often filter on one column. How would you add an index and keep it correct through updates and deletes? - After many deletes and updates, the data file keeps growing. How do you reclaim the space safely? - Two sessions write to the same table at once. What goes wrong, and what is the simplest correct fix?