我手写了一个Java内存数据库（一）：起因与架构

我手写了一个Java内存数据库一起因与架构文章标签#数据库 #Java #面试 #手写数据库 #B树前言使用MySQL多年后我产生一个疑问如果让我自己实现一个数据库能否做到本文将完整说明手写Java内存数据库的动机、选型、架构、核心设计为后续源码解析做铺垫。一、项目起因项目中存在大量高频查询场景需频繁从数据库拉取数据到内存做二次筛选数据库IO压力大、查询延迟高热点数据缓存需求强烈最初尝试用HashMap缓存但不支持范围查询如年龄20–30区间筛选无法满足业务刚需。因此决定自研B树索引 → 扩展为完整内存数据库引擎。最终成果完整B树实现插入/删除/分裂/合并/范围查询多字段联合索引引擎基于JSQLParser的SQL解析器软删除机制支持从关系型数据库加载数据并自动建索引无ORM、无Spring依赖纯Java手搓总代码量约2000行二、核心选型为什么是B树对比主流索引结构B树在范围查询、磁盘友好、平衡稳定上优势显著。数据结构查找复杂度范围查询插入/删除核心缺点红黑树O(logN)差需中序遍历O(logN)范围查询低效HashMapO(1)不支持O(1)无区间能力B树O(logN)极好叶子链表O(logN)结构维护稍复杂选型关键理由范围查询是刚需叶子节点形成双向链表可直接顺序遍历磁盘友好节点矮胖一个节点对应一个磁盘页未来落地磁盘IO极少综合稳定查找/插入/删除均为O(logN)性能均衡三、整体架构设计3.1 包结构com.bluepointsoft.database ├── Database.java # 数据库入口管理所有表 ├── ParseSql.java # SQL解析器SELECT/INSERT/UPDATE ├── btree/ │ ├── BPTree.java # B树封装 │ ├── Node.java # B树节点核心1054行 │ ├── Record.java # 记录模型 │ └── Tree.java # 树接口 ├── table/ │ ├── Table.java # 内存表索引管理CRUD │ ├── Row.java # 行数据支持软删除 │ └── RowSet.java # 结果集封装 ├── container/ │ └── MyList.java # 自定义long[]动态数组 └── fun/ └── Function.java # SQL函数桩to_char、to_number等3.2 查询数据流SQL → ParseSql解析 → Table定位表 → BPTree索引查找 → RowSet取数据 → Row返回结果四、B树节点核心设计4.1 Node类定义publicclassNode{// 是否叶子节点protectedbooleanisLeaf;// 是否根节点protectedbooleanisRoot;// 父节点protectedNodeparent;// 叶子前驱双向链表protectedNodeprevious;// 叶子后继双向链表protectedNodenext;// 关键字集合key → 多条记录protectedListEntryComparable,ArrayListObjectentries;// 子节点仅非叶子存在protectedListNodechildren;}4.2 关键设计点entries存ArrayList支持非唯一索引一个键对应多条记录叶子节点双向链表previous/next仅在叶子维护范围查询直接沿链表扫描children按需分配叶子节点无children节省内存节点内二分查找替代线性遍历大数据量下性能大幅提升五、核心查询实现5.1 节点内二分查找publicintsearch(ListEntryComparable,ArrayListObjectlist,Comparablekey){intlow0;inthighlist.size()-1;while(lowhigh){intmid(lowhigh)/2;EntryComparable,ArrayListObjectentrylist.get(mid);if(entry.getKey().compareTo(key)0){lowmid1;}elseif(entry.getKey().compareTo(key)0){highmid-1;}else{returnmid;}}return-1;}5.2 非叶子节点路由逻辑if(key.compareTo(entries.get(0).getKey())0){// 比最小键小走最左子树returnchildren.get(0).get(key);}elseif(key.compareTo(entries.get(entries.size()-1).getKey())0){// 比最大键大走最右子树returnchildren.get(children.size()-1).get(key);}else{// 中间区域二分定位子节点intbind1searchLess(entries,key);intbind2searchMore(entries,key);for(intiMath.max(bind2-1,0);ibind1;i){returnchildren.get(i).get(key);}}5.3 时间复杂度单节点查找O(logM)整树查找O(logN)综合O(logM × logN)MB树阶数N总记录数六、下篇预告节点设计与等值查询已完成B树真正难点在于插入时节点分裂删除时节点合并与借位下一篇将**逐行拆解B树插入逻辑**包含分裂阈值、中间节点升级、叶子链表维护等细节。