发起这个项目的起因， 是偶然看到一个网友发的 MongoDB 的 新闻，
我想， 像 MongoDB 这样的 非关系数据库 ，随时 都可以写 很多个，
真正 难写 的 是 关系数据库， 非关系数据库 都 很容易写，
所以， 我之前说， 关系数据库 才是 核心技术，
非关系数据库 不是 核心技术， 只能算 中间件 技术 。
非关系数据库 完全 可以 用 .Net 写， 效率 不会 低于 C++ 写的 。
国内开源界 缺少 这样 有技术含量 的 开源项目 。
未来 10 年内， New Sql 数据库 有望成为 大并发实时交易 场景 的 主角之一 ， 前景 是很好的 。
有兴趣的网友可以加入 384413261 这个 群， @K歌之王 就可以了 。
我简单画了个 架构图 ：
实现了 虚拟存储 这个模块后， 就可以按 对象 和 集合 方式 对 数据 进行存取 。
虚拟存储 就是 实现了 内存 + 文件 的 虚拟地址 和 存储功能 的 模块， 是 NewSql 数据库 的 核心模块 。
NewSql 数据库 是一个 对象模型， 也可以说是 内存模型， 也可以说是 树， 也可以说是 图 。
内存 里的 对象 是一个 树（图） 结构， NewSql 的 数据结构 也是一个 树（图） 结构 。
所以， 操作 NewSql 数据库 和 我们在 编程语言（如 C#） 里 操作 对象（集合） 是 相似 的 。
与之相比， 关系数据库 的 数据模型 和 数据存储 逻辑 是 很复杂的 ， 这就是 NewSql 数据库 比 关系数据库 更容易 实现的 原因 。
我们可以再 看看 存储引擎 的 架构图 ：
理想上， 存储引擎 可以提供 增删该查 数据 的 功能， 而 调用者 不需要 知道 数据 是在 内存 还是 文件 。
这需要 存储引擎 实现一个 虚拟地址空间， 这可以模仿 操作系统 的 虚拟内存， 采用 页式管理， 以 页（Page）为 内存 到 文件 之间的 数据 载入载出 单位 ， 比如 一个页 大小 64 KB 。
同时， 数据 存储到 文件上 需要 序列化， 数据项（节点） 之间 需要通过 地址 来 关联， 这个 地址 是 文件 里的 地址 。
而 数据 加载 到 内存 后， 数据项（节点） 之间 通过 内存 的 地址 来 关联（比如 引用关系， 或是 数组索引），
存储引擎 需要处理好 这个关系 。
所以， 从 职能 和 开发难度 来看， 存储引擎 都是 NewSql 数据库 的 核心模块 。
上述架构 是 一个 单体架构， 我们的目标应该是 一个 可以 通过 分布式 架构 获得 水平扩展 能力 的 NewSql 数据库 。
所以， 还需要 加上 分布式 和 水平扩展 的 特性 。
这个可以在后面 慢慢 加上 。
依据 “编写一些简单的模块， 把它们连接起来” 的 编程原则， 单体 写好了， 再加上 分布式 通信 和 协作算法 就行， 这样来看就不复杂 。
我之前对 关系数据库 作过一些 研究， 可以参考参考 ：
《我发起了一个 .Net 开源 数据库 项目 SqlNet》 https://www.cnblogs.com/KSongKing/p/9501739.html
文中 也 提到了 虚拟存储 。
在 文件 里 建立一个 地址空间， 相当于 在 文件 里 再实现一个 文件系统， 或者 内存堆，
这涉及到 堆 算法，
我之前写过一篇文章 《漫谈 C++ 的 内存堆 实现原理》 https://www.cnblogs.com/KSongKing/p/9527561.html ，
里面分析过 堆 算法 的 原理，
并且 在 《我发起了一个 .Net 开源 数据库 项目 SqlNet》 中也引用了 《漫谈 C++ 的 内存堆 实现原理》 这篇文章 。
但是 堆 的 算法 太复杂， 不适合我们使用 。
我们这次要换一个 简单 的 办法， 只需要有一个 线程 在 空闲的时候 对 堆 中的 “空闲空间” Free Space 排序就行， 从大到小排序，
这样， 当需要 申请分配 一块 空间 的时候， 只要 取 最大的 Free Space 来看， 如果 最大的 Free Space 大小足够， 就从 最大的 Free Space 上分配，
否则， 直接在 Data File 尾部 追加一块 “大块区域” div 。
当然， 这个算法 不是 最精确 的 管理 Free Space 或者说 “碎片” 的， 也不是 空间 上 最优 的， 但是 是 时间 上 是 有利 的 。
这没有关系， Sql Server 也是这样 。 Sql Server delete 删除资料后， Data File 并不会 缩小， 需要用专门的 “压缩卷” 操作 才能 回收碎片， 使 Data File 恢复到 实际数据 的 大小 。
Windows 文件系统 也是这样， 需要 定期 或 不定期 整理碎片 。
好的， 上面就是 基本 的 架构 。
我们来看看 技术方面 ，
New Sql 分析器 涉及 语法分析 ， 可以参考 《SelectDataTable》 https://www.cnblogs.com/KSongKing/p/9455216.html
但 这部分 要不要做， 还有待商榷 。 就是说 要不要 提供一个 New Sql 语言， 这还有待商榷 。
因为现在 在 代码 里 访问 关系数据库 都用 对象 的 方式了， 如 LiinQ， ORM ， 而 New Sql 数据库 的 数据 本身 就是 对象，
所以 好像 只要 提供 对象模型 的 接口方法 就可以了 ， 不需要 New Sql 语言 。
这样就类似 Redis 那样， 提供一个 协议， 不必 提供 语言 。
RPC 和 对象序列化 可以参考 《利用 MessageRPC 和 ShareMemory 来实现 分布式并行计算》 https://www.cnblogs.com/KSongKing/p/9490915.html ，
MessageRPC 是 一个简单的 RPC， ShareMemory 是一个 简单的 分布式缓存， 提供了 对象序列化 技术 。
并发架构 方面， 可以参考 《后线程时代 的 应用程序 架构》 https://www.cnblogs.com/KSongKing/p/10228842.html 。
增加一个 用例图 ：
事务模块， 是 虚拟存储 以外 第二个 复杂模块 和 核心模块 。
刚 网友说 NewSql 是支持 Sql 的， 我查了一下 百度百科， 确实是， 昨天只看了 ACID， 把 SQL 看漏了 。
百度百科 NewSql ： https://baike.baidu.com/item/NewSQL/9529614?fr=aladdin
支持 Sql 也可以 。 ^^
接下来我们讨论 虚拟存储 的 具体设计 ：
这是 虚拟存储 的 工作流程， 为了便于叙述， 我们给图里的一些地方标上了 序号 。
文件地址 指 对象 在 文件 中的 位置（Position）， 文件 中 数据的位置 是 通过 Position 表示的， 见 .Net 的 System.IO.File 的 Position 属性 。
1， 2， 5 处 表示 查询对象 时， 通过 虚拟地址 页表 将 对象 的 文件地址 转换为 内存地址， 若 对象 在 内存 中 存在， 则从 内存 读取， 若 对象 不在 内存， 则根据 文件地址 从 文件 中 读取 对象 到 内存 。 这部分流程 图中 的 注释 说的 很清楚了 。
3 处 表示 增删改 和 查询 一样， 都会先 查找到对象， 如果 对象 在 内存 里， 则 先更新 内存 里的 对象， 再 把 更新 写到 Update List（4 处）， 最后 把 Update Listt 里的更新批量写入数据库（6 处） 。
如果 对象 不在 内存 里， 则 直接将 更新 写入 Update List， 再把 Update Listt 里的更新批量写入数据库（6 处） 。
这部分 原理 其实 和 操作系统 虚拟内存 和 ORM 的 缓存 挺像的 。
我们来看看 虚拟地址 页表 的 原理图 ：
其实 上图 已经说的很清楚了 ， 呵呵呵 。
因为 我们的 NewSql 数据库 所使用的 内存 是 操作系统 的 虚拟内存， 所以， 我们的 页 的 大小 可以 设置 的 大一点 。
可以是 1 MB （操作系统 的 页 大小 可能是 64 KB）， 因为 操作系统 的 虚拟内存 会把 数据 从 内存 到 磁盘 之间 载入载出，
所以， 我们的 页 设置 的 大一点， 这样 从 内存 到 磁盘 之间 载入载出 数据 的 工作 就主要会由 操作系统 虚拟内存 来做，
避免 我们 在 操作系统 虚拟内存 的 基础 上 再次 频繁 的 载入载出 数据 。
假设 我们的 页表长度 是 1 M， 页大小是 1 MB 则可以管理 1 M * 1 MB = 1 TB 的 地址空间 。
怎么样？ 还可以吧 ？
页表 可以用 Hash 表 来做， 也可以用 线性表 。
我们这里用的是 线性表 。
Hash 表 省空间， 线性表 可能会更快一些 。
关于 页表 的 原理， 我在《浅谈 操作系统原理》 https://www.cnblogs.com/KSongKing/p/9495999.html 中 讨论过 操作系统 虚拟内存 的 原理， 其中也讨论了 页表 的 原理 。
文件地址 转换 为 内存地址 的 公式 ：
页下标 = (文件地址 / 页大小) 的 整数部分
偏移量 = (文件地址 / 页大小) 的 余数部分
页下标 就是 页 在 页表 中的 index， 通俗的讲， 就是 哪一个页 ；
偏移量 是 对象 在 页 中的位置， 也就是 对象 在 page.bytes 中的 位置， page.bytes[ 偏移量 ] 这就是 对象 的 第一个字节 。
这部分我在 《浅谈 操作系统原理》 中 提到过 。
当 对象 和 对象 之间 有关联时， 比如 Order 对象 中 包含了 一个 User 对象， 这样， Order 对象 中会有一个 字段 作为 指针， 指向 User 对象 。
这个 指针 的 值， 就是 User 对象 的 文件地址 。
对象 通过 序列化 为 byte[] 之后， 保存入文件 。
加载到 内存 时， 也是 byte[] 的 格式， 保存在 Page.bytes 中 。
所以， 我们要有一个地方 保存 对象 的 元数据， 即 包含了 哪些 字段， 每个 字段 的 序号（index）， 在 进入 底层处理前， 需要根据 元数据 把 对象 的 字段名 转换成 序号， 以 提高 处理效率 。
同时， 这里还包含了一个 序列化 的 格式， 根据 序列化格式 和 元数据 在 byte[] 中 查找 对象 和 对象的字段 。
序列化格式 和 元数据 有 密切的联系 。
元数据 类似 关系数据库 的 Table Schema， 或者 .Net 的 Class 元数据 。
在 关系数据库 中， 数据 是 表， 在 NewSql 数据库 中， 数据 是 对象 ， 所以， 元数据 就是 对象 的 类型（Type）， 该类型有哪些 字段（Field）， 字段的类型 。
类型 就类似 表定义， 字段 就类似 表 的 列 。
比如， 有一个 订单（Order）类型， 有 3 个 字段 ： ID， CreateUser， CreateDate 。
好吧， 直接写成 C# 里的 类 就行了 ：
class Order
{
int ID;
User CreateUser;
DateTime CreateDate;
}
就是这样 。
这就是 NewSql 数据库 中 对象 的 元数据 。
根据 元数据， 我们可以来 定义 序列化 格式， 比如 一个 Order 对象， 序列化 后 是 一个 byte[] ：
第 1 ~ 4 个 byte 是 ID 的 值， 4 个 byte 表示 32 位 整数， 即 int 类型，
第 5 ~ 12 个 byte 是 CreateUser， 这是一个 指针， 指向 一个 User 对象， 8 个 byte 表示一个 64 位 地址， 64 位 地址空间 可达到 16 EB 。
第 13 ~ 20 个 byte 是 CreateDate， 这是一个 DateTime 类型的值， .Net 里的 DateTime 的 时间值 好像就是用一个 64 位 整数表示的， 我也参考一下 。
我们需要对 Order 对象 的 字段 给出一个 序号（index），
比如，
ID 0，
CreateUser 1，
CreateDate 2，
然后， 根据 字段 的 序号（index） 和 字段 的 类型， 就可以计算出 字段 的 地址 ：
字段 的 开始地址 = 当前 字段 之前的 字段 的 长度 的 总和
字段 的 结束地址 = 字段 的 开始地址 + 字段 的 长度 - 1
比如 ID 字段 是 第一个字段， 它之前没有其它 字段， 所以， 它的 开始地址 是 0 ，
而 ID 字段 是 int 类型， 长度 是 4 个 byte， 所以， 它的 结束地址 是 0 + 4 - 1 = 3，
所以， 取 ID 字段的值 就会取 byte[0] , byte[1] , byte[2] , byte[3] 这 4 个 byte 。
在 C# 里， 可以用 BitConverter 类 把 int 类型 转换 为 byte[]， 也可以把 byte[] 转成 int 。
对于 User CreateUser; 这个 字段， 类似 C# 里的 “引用类型”， 这里存的是一个 指针， 指向 UserList 里的一个 User 对象， 这个 User 对象当然是 创建这张表单 的 那个 用户， 比如 张三 。
说起 UserList， 按照 百度百科 的 说法， NewSql 数据库 里是按 “对象 和 集合” 来 存储数据， 集合 就相当于 关系数据库 的表， 关系数据库 里的 一笔表记录 就相当于 集合里的 一个对象 。
不过 我这里 说的 通俗点， 我也不说 “集合” 了， 按照 C# 的 习惯， 我们 习惯 把 对象 放在 List<T> 里， 比如 List<Order> ，
所以， 我们 就 说 在 NewSql 数据库 里 数据 存放在 List 里 。
关系数据库 里的 Order 表 就相当于 NewSql 数据库 里的 List<Order> 。
这样应该 很清楚了 。 ^^
所以， 根据 元数据， 可以从 序列化 的 数据 byte[] 中， 查找 对象 的 字段值， 也可以还原出 对象 。 这就是 NewSql 数据库 检索数据， 或者说 处理数据 的 基础 。
那为什么 要 给 字段 编个序号（index）呢？ 这样是 为了 快速 的 处理数据， 在 编译 Sql 的时候， 就会把 字段名（如 “ID'”， “CreateUser”， “CreateDate”） 转换为 序号（index） 。
这个 序列化 格式， 是 将 数据 保存到 Data File 标准格式， 也就是说， 是 NewSql 数据库 存储数据 的 标准格式，
同时， 也可以作为 将 数据 返回 客户端 的 序列化 格式 。
当然， 返回 客户端 的话， 还需要把 元数据 也 返回 客户端， 这样 客户端 才能 反序列化 。
我们这里的 序列化 和 元数据 的 方式 类似 编译器， 因为我们这里对 NewSql 数据库 的 定位 是 用 内存模型 在 外部存储器 上 存储数据 。
接下来 说说 List 的 存储， 比如 List<User>， 跟 内存模型 一样， 或者说 跟 C# 一样，
不过 我们这里的 List 采用的是 链表， 所以， 严格的说， 这个 List 是一个 LinkedList（链表） 。
那么， 假设有 List<User> 里 有 3 个 对象，
张三
李四
王麻子
张三 里 会有一个 字段（比如 叫 “Next”）， 是一个 指针， 指向 李四，
李四 里 会有一个 字段（比如 叫 “Next”）， 是一个 指针， 指向 王麻子，
王麻子 里 也有一个 Next 字段， 不过现在是一个 空指针， 因为 王麻子 后面 没有对象了 。
为什么 要 采用 链式存储， 因为 链式存储 可以 快速 的 插入 删除 对象， 这在 大并发实时交易 的 场合 很重要 。
关系数据库 的 瓶颈 之一 就是 当 表 的数据很多时（比如 1000 万笔以上）， 频繁 的 Insert 导致 表 和 索引 的 一些数据 需要 移动 。
需要移动 的 数据 可能是 insert 的 资料 所插入 的 位置 附近 的 一些数据 。
具体的说， 可能是 insert 的 资料 所插入 的 Data Block 或者 Table Block 里的 数据 。
Data Block 或者 Table Block 里 会 存储 多笔 数据， 可能是 表数据， 也可能是 索引数据， 这些 数据 是 线性排列 的， 大家知道， 线性表 中 插入 一笔数据， 会导致 这笔数据 之后 的 所有 数据 全部 向后移动一个位置 。
而 链表 的 插入速度 很快， 时间复杂度 是 O(1) 。
这就是 我们 采用 链式存储 的 原因 。 我们希望， NewSql 数据库 可以通过 离散存储（如 链式存储）的 方式 突破 关系数据库 的 这一瓶颈 ， 让 大并发实时交易 成为 NewSql 数据库 的 一个 优势特点 。
也因此， 我们 对 NewSql 数据库 的 架构定位 是 离散存储 。
我们 再来 说说 元数据，
我们可以学习 Sql Server 这样， 把 元数据 也存在 表 里， NewSql 数据库 可以存在 List 里，
但这样就带来了一个问题 ： 是不是要 有一张 上帝创造 的 第一张表 ？
对于 NewSql 数据库， 就是 是不是要 有一个 上帝创造 的 第一个 List ？
是的， 是要有 这样一张表， 我们称之为 “Root Table”，
对于 NewSql 数据库， 我们可以称之为 “Root List” 。
这个 Root Table 或者说 Root List 的 元数据 是 “写死” 在 程序 里的 ， 当然 写在 配置文件 里 也可以 。
好的， NewSql 数据库 的 设计 就写到这里， 这是一个 基础架构， 不过在 这个 基础架构 上， 真的可以写一个 NewSql 数据库 喔 ~！
再补充一点， 我们来看看 String 类型 的 数据 和 String 类型 的 字段 的 存储方式， 上面说漏了 。
String 可以分为 定长 String 和 不定长 String 两种， 定长 String 相当于 Sql Server 里的 char(n)， 不定长 String 相当于 nvarchar ，
在 NewSql 数据库 里， 定长 String 是 值类型， 不定长 String 是 引用类型，
定长 String 和 不定长 String 的 存储格式 都是这样 ：
第 1 ~ 4 个 byte 表示一个 32 位 的 整数， 这个整数 表示 字符串 的 长度，
第 5 ~ n 个 byte 存储 字符串 的 内容 。 字符串 的 内容 是 按照某个编码（Encoding）转换成的 byte[] 。
定长 String 的 内容 部分 的 长度 是固定的， 所以 可能 造成 一些 空间的 浪费， 就好像 Sql Server 的 char(n)， 但因为 长度固定， 所以可以直接存在对象 里， 类似 C# 里的 “值类型” 。 直接存在 对象 里的话， 查询对象 时 效率 会 更高一些 。
不定长 String 的 内容 部分 的 长度 是不固定的， 所以 不定长 String 类型 的 字段 是 一个 指针， 指向 一个 不定长 String， 这类似于 C# 里的 “引用类型” 。
因为采用 内存模型 和 离散存储 的 架构， 所以 不定长 String 不需要像 Sql Server 的 nvarchar 一样 指定长度， 想存多长都可以 。
一句话， NewSql 数据库 的 时代， 是 离散存储 的 时代， 是 固态硬盘 的 时代， 是 “内存是硬盘， 硬盘是磁带” 的 时代， 是 用 内存模型 的 方式 在 外部存储器 上 存储 海量数据 的 时代 。