您现在的位置：程式碼之家 >> 數據庫知識 > >> MySQL 資料庫 >> MySQL 綜合教學

MySQL 詞法分析器內幕：手工打造的 Trie 樹關鍵字查找優化

編輯：MySQL 綜合教學

前言

MySQL SQL 解析包含詞法分析與語法分析。不同於通用的 Flex/Bison 組合，MySQL 的詞法分析器是**手工編寫的高優化 C 代碼**，核心在於關鍵字查找的 Trie 樹（前綴樹）實現。本文深入源碼級解析 gen_lex_hash 生成過程與 get_hash_symbol 查找邏輯。

一、架構概覽

1.1 入口函數

語法分析器：MYSQLparse() (由 Bison 生成 sql_yacc.yy)
詞法分析器：MYSQLlex() (手工編寫 sql_lex.cc)

1.2 核心調用鏈

sql_lex.cc:
  find_keyword()       -> get_hash_symbol()
  is_keyword()         -> get_hash_symbol()
  is_lex_native_function() -> get_hash_symbol()

lex_hash.h (生成):
  get_hash_symbol() -> sql_functions_map / symbols_map

二、關鍵字查找樹生成：gen_lex_hash

2.1 建構流程

讀取關鍵字陣列 (保存在 sql/lex.h 的 SYMBOL symbols[])
按關鍵字長度分組，構建 Trie 樹
將樹「壓平」為靜態陣列 symbols_map[] (無指針、緊湊佈局)
輸出 sql/lex_hash.h 供編譯期包含

2.2 CMake 構建規則

# sql/CMakeFiles/sql.dir/build.make
sql/lex_hash.h: sql/gen_lex_hash
    ./gen_lex_hash > lex_hash.h

gen_lex_hash 為編譯期工具，運行於構建機，產出的 lex_hash.h 隨源碼分發，運行期無依賴。

三、Trie 樹結構與壓平陣列表示

3.1 邏輯樹結構 (源碼註釋示例)

+-----------+-+-+-+
| len       |1|2|3|  <-- 按關鍵字長度分層
+-----------+-+-+-+
|first_char |0|0|a|  <-- 該長度層首字符最小值
|last_char  |0|0|d|  <-- 該長度層首字符最大值
|link       |0|0|+|  <-- 指向下一層節點陣列偏移
|
V
+----------+-+-+-+--+
| 1 char   |a|b|c|d |  <-- 長度=1 時的首字符節點
+----------+-+-+-+--+
|first_char|d|0|0|0 |
|last_char |n|0|0|-1|
|link      |+|0|0|+ |  <-- 指向長度=2 層
|
V
+----------+--+-+-+-+-+-+-+-+-+-+--+
| 2 char   |d |e|f|j|h|i|j|k|l|m|n |  <-- 長度=2 時的次字符節點
+----------+--+-+-+-+-+-+-+-+-+-+--+
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
|link      |+ |0|0|0|0|0|0|0|0|0|+ |
|          |  |                       |
V          V                       V
symbols[0]("ADD")          symbols[1]("AND")  ...

3.2 壓平陣列 `symbols_map[]` 結構

每個節點佔 4 位元組：

struct Node {
  uchar first_char;  // 該層首字符最小值
  uchar last_char;   // 該層首字符最大值
  uchar link;        // 下一層偏移 (0=無)
  uchar iresult;     // 索引: 0=未找到, >0 對應 symbols[] 索引
};

3.3 實例演進：逐步加入關鍵字

關鍵字集合	生成的 symbols_map 片段	說明
`{"&&"}`	`0,0,1,0, 0,0,0,0`	長度=2，首字符 '&'，找到 symbols[0]
`{"&&", "<"}`	`0,0,1,0, 0,0,0,0`	長度=1 新增 '<'，iresult=1 指向 symbols[1]
`{"&&", "<", "<="}`	`0,0,1,0, '&','<',2,0, 0,0,0,0, 0,0,3,0...`	長度=2 層擴展，'&' 指向 "&&"，'<' 指向下一層 '='
`{"&&", "<", "<=", "<>"}`	`..., '=', '>', 25, 0, 0,0,2,0, 0,0,3,0...`	長度=3 層新增 '=' 和 '>'，分別指向 symbols[2]、symbols[3]

四、查找算法：get_hash_symbol()

4.1 核心邏輯 (偽代碼)

function get_hash_symbol(keyword, length):
  node = root[length]          // 根據長度進入對應層
  if not node: return NOT_FOUND

  for i = 0 to length-1:
    c = keyword[i]
    if c < node.first_char or c > node.last_char:
      return NOT_FOUND
    
    offset = (c - node.first_char) * 4
    node = symbols_map[node.link + offset]
    
    if i == length-1:         // 最後一字符
      if node.iresult > 0:
        return symbols[node.iresult - 1]  // 找到
      else:
        return NOT_FOUND
    
    if node.link == 0:        // 中間無下一層
      return NOT_FOUND

  return NOT_FOUND