自己动手写SQL执行引擎 前言
在阅读了大量关于数据库的资料后，笔者情不自禁产生了一个造数据库轮子的想法。来验证一下自己对于数据库底层原理的掌握是否牢靠。在笔者的github中给这个database起名为Freedom。
整体结构既然造轮子，那当然得从前端的网络协议交互到后端的文件存储全部给撸一遍。下面是Freedom实现的整体结构，里面包含了实现的大致模块:
最终存储结构当然是使用经典的B+树结构。当然在B+树和文件系统block块之间的转换则通过Buffer(Page) Manager来进行。当然了，为了完成事务，还必须要用WAL协议，其通过Log Manager来操作。
Freedom采用的是索引组织表，通过DruidSQL Parse来将sql翻译为对应的索引操作符进而进行对应的语义操作。 MySQL Protocol结构
client/server之间的交互采用的是MySQL协议，这样很容易就可以和mysql client以及jdbc进行交互了。
query packetmysql通过3byte的定长包头去进行分包，进而解决tcp流的读取问题。再通过一个sequenceId来再应用层判断packet是否连续。
mysql协议部分最复杂的内容是其对于result set的读取，在NIO的方式下加重了复杂性。
Freedom通过设置一系列的读取状态可以比较好的在Netty框架下解决这一问题。
还有一个较简单的是对row格式进行读取，如上图所示,只需要按部就班的解析即可。
由于协议解析部分较为简单，在这里就不再赘述。 SQL Parse
Freedom采用成熟好用的Druid SQL Parse作为解析器。事实上，解析sql就是将用文本表示
的sql语义表示为一系列操作符(这里限于篇幅原因，仅仅给出select中where过滤的原理)。
例如where后面的谓词就可以表示为一系列的以树状结构组织的SQL表达式，如下图所示:
当access层通过游标提供一系列row后，就可以通过这个树状表达式来过滤出符合where要求的数据。Druid采用了Parse中常用的visitor很方便的处理上面的表达式计算操作。 对join的处理
对join最简单处理方案就是对两张表进行笛卡尔积，然后通过上面的where condition进行过滤，如下图所示:
由于Freedom采用的是B+树作为底层存储结构，所以可以通过where谓词来界定B+树scan(搜索)的范围(也即最大搜索key和最小搜索key在B+树种中的位置)。考虑sql
select a.*,b.* from t_archer as a join t_rider as b where a.id>=3 and a.id<=11 b.id and b.id>=19 b.id<=31那么就可以界定出在id这个索引上,a的scan范围为[3,11],如下图所示:
b的scan范围为[19,31],如下图所示(假设两张表数据一样，便于绘图):
scan少了从原来的15*15(一共15个元素)次循环减少到4*4次循环,即循环次数减少到7.1%
当然如果存在join condition的话，那么Freedom在底层cursor递归处理的过程中会预先过滤掉一部分数据，进一步减少上层的过滤。
B+Tree的磁盘结构 leaf磁盘结构Freedom的B+Tree是存储到磁盘里的。考虑到存储的限制以及不定长的key值，所以会变得非常复杂。Freedom以page为单位来和磁盘进行交互。叶子节点和非叶子节点都由page承载并刷入磁盘。结构如下所示:
一个元组(tuple/item)在一个page中分为定长的ItemPointer和不定长的Item两部分。
其中ItemPointer里面存储了对应item的起始偏移和长度。同时ItemPointer和Item如图所示是向着中心方向进行伸张，这种结构很有效的组织了非定长Item。 leaf和node节点在Page中的不同
虽然leaf和node在page中组织结构一致，但其item包含的项确有区别。由于Freedom采用的是索引组织表，所以对于leaf在聚簇索引(clusterIndex)和二级索引(secondaryIndex)中对item的表示也有区别,如下图所示:
其中在二级索引搜索时通过secondaryIndex通过index-key找到对应的clusterId,再通过
clusterId在clusterIndex中找到对应的row记录。
由于要落盘，所以Freedom在node节点中的item里面写入了index-key对应的pageno,
这样就可以容易的从磁盘恢复所有的索引结构了。 B+Tree在文件中的组织