阅读时间: 20 分钟 | 难度: ⭐⭐⭐ | 实战性: ★★★★☆
背景: 当你在 MySQL 中执行
CREATE INDEX idx_name ON users(name)
时，这条 SQL 语句是如何被解析、编译并最终创建出 B+Tree 索引的？本文从 MiniToadB 的实际代码出发，完整剖析索引语法的词法定义、语法解析、数据存储创建，包含真实测试数据和踩坑记录。
作者介绍
数据库内核专家 | 分布式系统架构师
深耕数据库内核架构设计与开发十余年，主导研发多款高性能分布式数据库，攻克高并发、低延迟等核心技术难题。
现倾力打造《从零手写数据库》系列教程，首次系统性公开数据库内核源码级实现细节，从存储引擎到分布式事务，手把手拆解核心模块。
无论你是数据库开发者、系统架构师，还是对底层技术充满好奇的极客，这里都有你想要的「硬核干货」！
系列文章
【手写数据库核心揭秘系列】
一、AST 节点结构：语法树的构建
接上一篇索引的词法、语法规则介绍之后，接着介绍索引语法节点的定义与创建。
1.1 CreateIndexStmt 结构体
typedef struct CreateIndexStmt
{
NodeType type; // T_CreateIndexStmt (用于类型识别)
char *indexName; // 索引名称 (如 "idx_email")
char *tableName; // 所在表名 (如 "users")
Node *columnList; // 索引列列表 (T_List of ColumnName)
IndexAlgorithmType indexType; // 算法类型 (IAT_BTREE)
int isUnique; // 1=UNIQUE, 0=普通索引
Node *includeList; // 覆盖列列表 (可为 NULL)
} CreateIndexStmt;
1.2 AST 解析示例（可视化）
输入 SQL：
CREATE UNIQUE INDEX idx_comp ON users(name, age) INCLUDE (id);
生成的 AST 结构：
CreateIndexStmt (NodeType: T_CreateIndexStmt)
├── indexName: "idx_comp" [char*]
├── tableName: "users" [char*]
├── columnList: T_List [Node*]
│ ├── [0]: ColumnName("name") [ColumnName*]
│ └── [1]: ColumnName("age") [ColumnName*]
├── indexType: IAT_BTREE [enum]
├── isUnique: 1 [int] ★
└── includeList: T_List [Node*]
└── [0]: ColumnName("id") [ColumnName*]
1.3 其他相关 AST 节点
DropIndexStmt（删除索引）
typedef struct DropIndexStmt
{
NodeType type;
char *indexName; // 要删除的索引名
} DropIndexStmt;
// SQL: DROP INDEX idx_name;
ReIndexStmt（重建索引）
typedef struct ReIndexStmt
{
NodeType type;
char *relationName; // 表名或索引名
int reindexType; // 0=INDEX, 1=TABLE
} ReIndexStmt;
// SQL: REINDEX TABLE users;
// SQL: REINDEX INDEX idx_name;
二、执行器入口：从 AST 到 B+Tree 创建
2.1 完整执行流程图
用户输入: CREATE INDEX idx_name ON users(name);
│
▼
┌─────────────────────────────────────────────────────────────┐
│ Phase 1: 词法分析 (Flex) │
│ sqlscanner.l → Token 流 │
└─────────────────────────────┬───────────────────────────────┘
│ Token 流
▼
┌─────────────────────────────────────────────────────────────┐
│ Phase 2: 语法分析 (Bison) │
│ sqlgram.y → CreateIndexStmt AST │
└─────────────────────────────┬───────────────────────────────┘
│ AST 节点
▼
┌─────────────────────────────────────────────────────────────┐
│ Phase 3: 执行器调度 (executor.c) │
│ │
│ ExecCreateIndexStmt(AST) │
│ │ │
│ ├── Step 1: CreateIndex() │
│ │ ├── OpenRelation("users") │
│ │ ├── CreateIndexRelation() │
│ │ ├── BtInitIndex() ──────────────────────┐ │
│ │ │ └── 分配页 1: 元信息页 (BTreeInfo) │ │
│ │ └── RegisterIndexToTable() │ │
│ │ │ │
│ └── Step 2: ExecReBuildIndex() │ │
│ ├── ExecSeqScan() → 遍历 users 表 │ │
│ └── ExecIndexInsert() │ │
│ └── BtInsertTuple() ◄──────────────────┘ │
│ │ │
│ ▼ │
│ B+Tree 已创建完成 │
└─────────────────────────────────────────────────────────────┘
2.2 核心函数详解
ExecCreateIndexStmt() - 执行器入口
int ExecCreateIndexStmt(Node *rootNode)
{
int ret = 0;
// Step 1: 创建索引元信息（分配页面、初始化元信息页）
ret = CreateIndex(rootNode);
if(ret < 0) {
printf("CreateIndex failure\n");
return ret;
}
// Step 2: 扫描基表数据，构建索引内容
ret = ExecReBuildIndex(rootNode);
if(ret < 0) {
printf("ExecReBuildIndex failure\n");
return ret;
}
printf("CREATE INDEX success\n");
return MINITOADB_SUCCESS;
}
设计决策：为什么分两步？
Step 1 失败：回滚元信息，不影响原表数据 Step 2 失败：索引已创建但为空，可后续 REINDEX 修复 原子性保证：两步都成功才输出 "success"
CreateIndex() - 元信息初始化
int CreateIndex(Node *rootNode)
{
CreateIndexStmt *stmt = (CreateIndexStmt*)rootNode;
IndexRelationInfo *indexInfo = NULL;
RelationInfo *relInfo = NULL;
int ret = 0;
// 1. 打开基表（验证表是否存在）
relInfo = OpenRelation(stmt->tableName);
if(relInfo == NULL) {
printf("table %s is not found.\n", stmt->tableName);
return-1;
}
// 2. 创建索引关系信息（内存结构）
indexInfo = CreateIndexRelation(relInfo, stmt);
if(indexInfo == NULL) {
return-1;
}
// 3. 初始化 B+Tree（分配元信息页）
ret = BtInitIndex(indexInfo, stmt->isUnique);
if(ret < 0) {
return ret;
}
// 4. 注册索引到表的索引列表
RegisterIndexToTable(relInfo, indexInfo);
return0;
}
关键操作：
OpenRelation()
：打开堆表文件，读取表结构CreateIndexRelation()
：创建IndexRelationInfo
内存结构BtInitIndex()
：调用 B+Tree 模块，分配页 1 作为元信息页RegisterIndexToTable()
：将索引添加到RelationInfo->indexList
ExecReBuildIndex() - 数据重建
int ExecReBuildIndex(Node *rootNode)
{
CreateIndexStmt *stmt = (CreateIndexStmt*)rootNode;
ScanNode seqScanNode = {0};
TableRefInfo tblRefInfo = {0};
ResultNode *resultList = NULL;
RelationInfo *relInfo = NULL;
TupleHeader *tup = NULL;
DataPosition dataPos = {0};
// 1. 设置顺序扫描参数
tblRefInfo.tblName = stmt->tableName;
tblRefInfo.scanPos = (ScanNode*)&seqScanNode;
// 2. 循环扫描表的每一行
do {
// 2.1 获取下一行元组
resultList = (ResultNode*)ExecNodeProc((Node*)&seqScanNode);
if(resultList == NULL)
break; // 扫描结束
tup = resultList->tup;
// 2.2 获取元组在堆表中的物理位置
dataPos.pageNum = tup->pageNum;
dataPos.item_offset = tup->item_offset;
// 2.3 插入到所有相关索引（包括刚创建的索引）
ExecIndexInsert(relInfo, &dataPos, tup);
// 2.4 释放结果节点内存
ReleaseResultNode((Node*)resultList);
tup = NULL;
} while(1); // 直到 ExecSeqScan 返回 NULL
return0;
}
性能特征：
时间复杂度：O(N)，N 为表中行数 对每行执行一次 ExecIndexInsert()
→BtInsertTuple()包含 B+Tree 查找位置 + 写入叶子的开销
三、开发过程中的踩坑记录
坑 #1：AST 节点字段未初始化导致崩溃
问题描述： 执行 CREATE INDEX idx ON users(name);
时崩溃：
Segmentation fault (core dumped)
调试过程： 使用 GDB 回溯调用栈：
#0 0x0000555555556xxx in ExecIncludeListCheck (node=0x0)
#1 0x0000555555555xxx in ExecCreateIndexStmt (rootNode=0x5555555789a0)
发现 includeList
字段值为 NULL
，但代码未做空指针检查。
根本原因：NewNode()
使用 memory_alloc()
分配内存，但不会自动清零：
// 错误实现 ❌
CreateIndexStmt *node = NewNode(CreateIndexStmt);
// 此时 node->includeList 是随机值（可能是 0x5555555789a0 或其他垃圾值）
// 如果随机值非 NULL，执行器会误判为有 INCLUDE 列表
修复方案：
方法 1：手动清零（推荐）：
// 正确实现 ✅
CreateIndexStmt *node = NewNode(CreateIndexStmt);
memset(node, 0, sizeof(CreateIndexStmt)); // ★ 手动清零
node->type = T_CreateIndexStmt;
方法 2：使用封装宏：
#define NEW_NODE(type) \
({ type *_node = NewNode(type); \
memset(_node, 0, sizeof(type)); \
_node->type = type; \
_node; })
// 使用方式
CreateIndexStmt *node = NEW_NODE(CreateIndexStmt);
影响范围： 此问题影响所有 AST 节点类型，包括：
CreateIndexStmtDropIndexStmtSelectStmtInsertStmt...
最终修复：系统性修改所有 NewNode()
调用点，确保字段初始化。
坑 #2：CREATE INDEX 报错但仍创建成功
问题描述： 测试输出显示矛盾结果：
error: syntax error
CREATE INDEX success
原因分析：
语法分析阶段报告了 warning（非 fatal error） 但语法分析器最终还是成功生成了 AST 执行器正常创建了索引
可能的原因：
测试脚本中的 SQL 语句有额外空格或特殊字符 词法分析器的标识符规则过于宽松 语法规则的错误恢复机制生效了
修复方案： 严格化词法规则，过滤非法字符：
// 原来的规则（太宽松）❌
identify [a-zA-Z][a-zA-Z0-9_]*
// 改进后的规则（更严格）✅
identify [a-zA-Z_][a-zA-Z0-9_]*
并在语法分析器中增加 %define error_verbose
以输出详细错误信息。
文章转载自开源无限，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
