【手写数据库核心揭秘系列】第10节 SQL解析树的结构，语言识别与程序执行之间的桥梁

解析树的结构

一、概述

SQL语句以字符串的形式输入解析器后，经过flex词法解析生成token的序列，进入bison语法分析，经过语法规则的匹配得到解析树，解析树也是整个解析器的输出结果。

解析树通过倒立的树形结构来描述SQL中各个基本组成的语法关联关系，从树根向下逐层展开，直到用户标识和数据值为叶子节点。

在数据库中，基于解析树来生成SQL的执行计划，它也是一个树形结构，同时还可以进行重写优化等调整，才会进入到SQL的真正执行阶段。

因此解析树是SQL语言与数据库软件之间的桥梁，是对SQL语言理解转换成的内部表达形式。

二、解析树的原理

解析树由树的一系列的节点构成，节点的类型代表了SQL中的最小语法子句，节点中的数据就是子句的内容。

这一系列不同类型的节点，由多层链表的数据结构将它们组织成树的形式，由根节点来记录一颗完整的解析树。

例如SQL语句“SELECT ID, NAME, AGE FROM STUDENT;”对应的解析树形式如下图所示