我手写了一个 Java 内存数据库（四）：索引引擎、SQL 解析与总结
前三篇把 B+ 树写清楚了。这篇把 B+ 树组装进索引引擎，加上 SQL 解析和软删除，形成完整的数据流，最后聊聊做完了回头看的心得。
一、索引引擎：Table + B+ 树怎么配合
表结构
publicclassTable{privaterowSet data=newrowSet();// 数据存储privateList<HashMap<String,Object>>mete;// 字段元数据privateStringname;// 表名privateHashMap<String,BPTree>index=newHashMap<>();// 字段 → B+ 树索引privateStringsql;// 加载 SQL}一个设计决策：一张表可以建多个 B+ 树索引，每个索引对应一个字段。比如有 10 万行人员数据，可以在"身份证号"字段建一个 B+ 树，在"年龄"字段再建一个，互不干扰。
从关系型数据库加载
Table.init()的功能是从传统 RDBMS 把数据拉到内存，同时建好索引：
Connectionconn=session.getSession().getConnection();ResultSetresult=conn.createStatement().executeQuery(sql);ResultSetMetaDatarsmd=result.getMetaData();// 先读元数据for(inti=0;i<rsmd.getColumnCount();i++){HashMap<String,Object>obj1=newHashMap<>();mete.add(obj1);obj1.put("name",rsmd.getColumnName(i+1));obj1.put("type",rsmd.getColumnTypeName(i+1));}// 逐行加载while(result.next()){Rowrow1=newRow();data.append(row1);intsize=data.getList().size()-1;for(inti=0;i<rsmd.getColumnCount();i++){Stringkey=rsmd.getColumnName(i+1);Objectvalue=String.valueOf(result.getObject(i+1));row1.put(key,value);// 有索引的字段，同步插入 B+ 树if(index.get(key)!=null){longvaluekey;if(valueinstanceofInteger||valueinstanceofLong)valuekey=Long.parseLong(String.valueOf(value));elsevaluekey=value.hashCode();index.get(key).insertOrUpdate(valuekey,size,false);}}}这里有个关键点：B+ 树索引存的不是数据本身，而是size（数据在 rowSet 里的下标）。查询时先通过 B+ 树找到下标，再用下标去 rowSet 取数据。这样多个索引可以指向同一行数据，不用存多份。
索引查询
等值查询：
publicObjectget(Objectname,Objectval){BPTreeindex1=index.get(name);if(index1!=null){longkey=(valinstanceofInteger||valinstanceofLong)?Long.parseLong(String.valueOf(val)):val.hashCode();ArrayList<Object>addrs=(ArrayList<Object>)index1.get(key);List<Object>list=newArrayList<>();for(inti=0;i<addrs.size();i++){list.add(data.get(Integer.parseInt(String.valueOf(addrs.get(i)))));}returnlist;}else{// 无索引：全表扫描（这个我还没实现）}returnnull;}范围查询也类似，getLessThen/getMoreThen/getMoreAndLessThen返回下标集合，再逐个取数据。
非数字类型的索引
if(valueinstanceofInteger||valueinstanceofLong)valuekey=Long.parseLong(String.valueOf(value));elsevaluekey=value.hashCode();字符串等非数字类型用hashCode()做 B+ 树的 key。这在数据量不大时没问题，但hashCode存在碰撞的可能（两个不同字符串算出同一个值）。如果要做生产级，应该换成字符串本身的比较，或者用前缀索引。这个是我后来意识到的一个隐患。
二、SQL 解析器
为什么自己搞 SQL 解析
本来想直接让调用方传 Table 名和字段名，但想着既然做数据库，至少得支持 SQL 字符串输入吧。没自己写词法分析器，用了 JSQLParser 库，它能把 SQL 文本解析成抽象语法树（AST），我再从 AST 里提取各部分：
publicstaticList<String>select_items(Stringsql)throwsJSQLParserException{CCJSqlParserManagerparserManager=newCCJSqlParserManager();Selectselect=(Select)parserManager.parse(newStringReader(sql));PlainSelectplain=(PlainSelect)select.getSelectBody();List<SelectItem>selectitems=plain.getSelectItems();List<String>str_items=newArrayList<>();for(inti=0;i<selectitems.size();i++){str_items.add(selectitems.get(i).toString());}returnstr_items;}提取了什么
SELECT：字段列表、表名、JOIN、WHERE、GROUP BY、ORDER BY
INSERT：表名、列名、值
UPDATE：表名、列名、值、WHERE
举个例子：
Stringsql="SELECT a.aab001, b.aab002 FROM ab01 a, ab02 b WHERE a.aab001 = b.aab001";List<String>items=praseSql.select_items(sql);// ["a.aab001", "b.aab002"]List<String>tables=praseSql.select_table(sql);// ["ab01", "ab02"]Stringwhere=praseSql.select_where(sql);// "a.aab001 = b.aab001"有了这些信息，就能知道查哪张表、用什么字段过滤、要不要走索引。不过目前 WHERE 条件的执行还是比较简单，复杂的多表 JOIN 还没实现。
三、软删除
为什么不能真删
这个坑我是实打实踩过的。一开始 delete 直接从ArrayList里 remove，结果删了之后后面所有元素的下标全变了——B+ 树索引里存的地址全乱了。
改成了软删除：
publicclassRow{privateHashMap<String,Object>data=newHashMap<>();privatebooleanisDelete=false;publicObjectget(Stringkey){returnisDelete?null:data.get(key);// 标记删除后返回 null}}rowSet 层也是标记，不真删：
publicsynchronizedvoiddelete(inti){list.get(i).setDelete(true);// 只标记count--;}后来查资料发现 MySQL InnoDB 也是这么干的——DELETE MARK标记删除，然后purge线程后台清理。算是思路不谋而合。
四、数据库入口
publicclassdatabase{privatestaticHashMap<String,Table>tables=newHashMap<>();publicstaticintload(Stringname){Tableobj=tables.get(name);if(obj==null){obj=newTable();tables.put(name,obj);}obj.init(name);return0;}}很简单的单例，按表名管理所有 Table。调用database.load("ab01")就能把 RDBMS 里的 ab01 表拉到内存并建好索引。
五、一个细节：自定义 long[] 动态数组
publicclassmyList{privatelong[]list=newlong[2];privateintcount=0;publicvoidadd(Longval){if(count+1>list.length){long[]dest=newlong[list.length+1];// 每次扩容 +1System.arraycopy(list,0,dest,0,list.length);dest[list.length]=val;list=dest;}else{list[count]=val;}count++;}}这个是当时为了减少 Long 对象的内存开销写的（long[]比ArrayList<Long>省一半内存）。扩容策略是 +1，不是 ArrayList 的 1.5 倍。优点是内存精确，缺点是每次扩容都触发数组拷贝。数据量已知时好用，不确定数据量时不合适。
六、整体数据流
┌──────────────────────────────────────────────┐ │ database │ │ HashMap<String, Table> │ │ ┌──────────────┐ ┌──────────────┐ │ │ │ Table "ab01" │ │ Table "ab02" │ │ │ │ │ │ │ │ │ │ rowSet │ │ │ │ │ │ [Row, Row] │ │ │ │ │ │ │ │ │ │ │ │ index: │ │ │ │ │ │ "aab001" → │ │ │ │ │ │ BPTree │ │ │ │ │ │ ┌────────┐│ │ │ │ │ │ │ Node ││ │ │ │ │ │ │ (root) ││ │ │ │ │ │ └────────┘│ │ │ │ │ └──────────────┘ └──────────────┘ │ └──────────────────────────────────────────────┘ 查询： SQL → praseSql 解析 → Table.get(field, value) → BPTree.get(key) 返回下标 → rowSet.get(下标) 返回 Row七、做完了回头看
做对了的
| 设计 | 当时怎么想的 |
|---|---|
| B+ 树完整实现 | 既然要写就写全套，插入分裂、删除合并、范围查询都做了 |
| 索引存下标 | 避免数据冗余，多个索引共享同一份数据 |
| 软删除 | 踩了真删的坑之后改的，下标不能变 |
| 预留空间 | 批量插入时分裂太频繁，加了 10% 预留 |
| 二分查找变体 | searchless/searchmore让范围查询在节点内也高效 |
做得不够的
| 问题 | 如果重做会怎么改 |
|---|---|
| 没有持久化 | 加 WAL 或定期序列化到磁盘 |
| 没有事务 | 引入 MVCC + undo log |
| 非叶子节点路由线性扫描 | 应该也用二分 |
| 没有查询优化器 | 至少做个索引选择性判断 |
| myList 扩容 +1 | 改成 1.5 倍几何增长 |
| hashCode 做索引 key | 有哈希冲突风险，应该用字符串比较 |
| SQL 函数都是空实现 | to_char、to_date 没来得及写 |
最大收获
这个项目让我真正理解了：
- 为什么 MySQL 用 B+ 树而不是 B 树（B 树非叶子节点也存数据，一个页能放的 key 更少，树更高）
- 为什么"最左前缀原则"对联合索引有效（B+ 树按 key 排列，跳过第一列就没法二分了）
- 为什么索引建多了会影响写入性能（每次插入要更新所有索引的 B+ 树）
- EXPLAIN 里的
range类型扫描是怎么工作的
这些知识看书和博客也能知道，但手写一遍之后，感觉完全不一样。
系列回顾：
- [（一）起因与架构] — 为什么做、选 B+ 树的原因、节点设计、等值查询
- [（二）B+ 树的插入与分裂] — 分裂机制、级联传播、validate 校准- （[三）删除、合并与范围查询] — 借位合并、三种范围查询、踩的坑
系列：我手写了一个 Java 内存数据库（共 4 篇）
