In-Memory Database: Insert, Query, and Indexing

Context

You are to design a minimal, single-process, in-memory database to be embedded in a service. The database manages multiple named tables with simple schemas and must support:

• write: insert(table, record)
• read: query(table, columns_to_project, conditions=[(column, operator, value)], order_by=(columns, ascending))

Assume:

• Records are dictionaries keyed by column name.
• Each table has a defined schema (column names and basic types like int/float/string), but you may keep type handling simple.
• Operators include: =, !=, <, <=, >, >=, IN (optional). Combine conditions with AND semantics.
• order_by takes one or more columns and a boolean ascending flag.
• Single-threaded execution is fine; you do not need transactions or persistence.

Tasks

1. Design the in-memory data structures and algorithms to implement insert and query.
2. Provide an implementation sketch (pseudocode or a compact, idiomatic language like Python/Go/Java) showing the core logic.
3. Extend the design to explain how indexes would be built and used to speed up WHERE (conditions) and ORDER BY queries, including:
   • What index types you would support and why.
   • How inserts update indexes.
   • How the query planner chooses which index to use for different predicates and orderings.
   • Complexity trade-offs and edge cases.