内存SQL小系统：Insert、投影、Where和多列Order

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练固定schema、所有值string，insert完整一行；query接列名、单predicate和order_by字段列表。
• 字符串比较为字典序，age="10"小于"2"；正式要求数值比较时必须引入列类型而非局部强转。

解题路线

1. insert校验列集合与值类型并copy，隔离调用方后续修改。query先where过滤再对完整row排序，最后projection；先projection会丢order所需字段。
2. 多列排序利用稳定sort从最后键到第一键，各列可升/降；相同所有键保留插入顺序。where仅=/>/<，不支持OR/AND/null三值逻辑，扩展需明确定义。
3. delete要求显式predicate，先校验再filter出保留行并返回删除数；省略predicate不默认删全表。数据库名/多表可外层map管理，索引可优化等值filter，但需同步更新。完整SQL文本parser、事务、并发属于额外scope，不因题叫数据库就承诺全部。

手动走一遍

select name,birthday where birthday>1900-01-01：ISO日期格式可按字典序比较，但其他日期格式未必。按name升序、age降序排序后只输出name，仍需用原row的age做二级排序。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Table:
    def __init__(self,columns):
        if len(set(columns))!=len(columns):raise ValueError("duplicate columns")
        self.columns=tuple(columns);self.rows=[]
    def insert(self,row):
        if set(row)!=set(self.columns) or any(type(v) is not str for v in row.values()):raise ValueError("string row schema")
        self.rows.append(dict(row))
    def query(self,columns,where=None,order_by=()):
        if any(c not in self.columns for c in columns) or any(c not in self.columns for c,desc in order_by):raise ValueError("unknown column")
        compare={'=':lambda a,b:a==b,'>':lambda a,b:a>b,'<':lambda a,b:a<b}
        if where is not None:
            col,op,value=where
            if col not in self.columns or op not in compare or type(value) is not str:raise ValueError("predicate")
        selected=[row for row in self.rows if where is None or compare[where[1]](row[where[0]],where[2])]
        for col,descending in reversed(order_by):selected.sort(key=lambda row:row[col],reverse=descending)
        return [{col:row[col] for col in columns} for row in selected]
    def delete(self,where):
        col,op,value=where
        compare={'=':lambda a,b:a==b,'>':lambda a,b:a>b,'<':lambda a,b:a<b}
        if col not in self.columns or op not in compare or type(value) is not str:raise ValueError('predicate')
        keep=[row for row in self.rows if not compare[op](row[col],value)]
        removed=len(self.rows)-len(keep);self.rows=keep;return removed

复杂度

n行、p投影列、k排序字段，扫描O(n)、排序O(k nlogn)保守、输出O(np)；空间O(n+np)，字符串比较长度成本另计。

易错点与追问

容易失分的边界

• 字符串数字与数值排序结果不同。
• 修改原row污染内部表，或返回内部引用让用户改表。

继续深挖

• Where支持AND/OR时怎样表示predicate AST？
• 按非投影列排序与limit能否推下，依哪些规则？