1

我正在阅读mysql的gen_lex_hash.cc，但我不知道解释：

提出算法的想法见 Donald E. Knuth 第 3 卷“排序和搜索”的“计算机编程艺术” （第 6.3 章“数字搜索” - 章节名称和编号 是从俄语版回译的 :)） 

as illustration of data structures, imagine next table:

static SYMBOL symbols[] = {
  { "ADD",              SYM(ADD),0,0},
  { "AND",              SYM(AND),0,0},
  { "DAY",              SYM(DAY_SYM),0,0},
};

for this structure, presented program generate next searching-structure:

+-----------+-+-+-+
|       len |1|2|3|
+-----------+-+-+-+
|first_char |0|0|a|
|last_char  |0|0|d|
|link       |0|0|+|
                 |
                 V
   +----------+-+-+-+--+
   |    1 char|a|b|c|d |
   +----------+-+-+-+--+
   |first_char|d|0|0|0 |
   |last_char |n|0|0|-1|
   |link      |+|0|0|+ |
               |     |
               |     V
               |  symbols[2] ( "DAY" )
               V
+----------+--+-+-+-+-+-+-+-+-+-+--+
|    2 char|d |e|f|j|h|i|j|k|l|m|n |
+----------+--+-+-+-+-+-+-+-+-+-+--+
|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
        symbols[0] ( "ADD" )  symbols[1] ( "AND" )

for optimization, link is the 16-bit index in 'symbols'
or search-array..

从上面的流程中，我无法理解细节，也找不到任何详细的解释。

为了理解这一点，我调试了程序gen_lex_hash，但它没有任何帮助，例如：

  1. 0,-1意味着什么？

任何建议将被认真考虑！

4

1 回答 1

1

这似乎是“计算机编程艺术”第 3 卷： Donald Knuth 的排序和搜索，第 6.3 章（从第 492 页开始）中的“trie 搜索”算法的实现。

它似乎用于有效地识别查询中的 SQL 关键字。

https://dev.mysql.com/doc/internals/en/sql-directory.html

于 2017-08-17T04:36:37.427 回答