mysql의 gen_lex_hash.cc 알고리즘을 어떻게 이해합니까?

mysql의 gen_lex_hash.cc 알고리즘을 어떻게 이해합니까?

mysql의 gen_lex_hash.cc를 읽고 있는데 설명을 모르겠습니다.

제시된 알고리즘의 개념은 다음과 같습니다. 도널드 E. 커누스의 "컴퓨터 프로그래밍의 기술 제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무슨 뜻입니까?

어떤 조언이든 감사하겠습니다!

이것은 컴퓨터 프로그래밍의 기술, 3권: Donald Knuth의 정렬과 검색, 6.3장(492페이지부터 시작)의 "트리 검색" 알고리즘의 구현으로 보입니다.

쿼리 내에서 SQL 키워드를 효율적으로 식별하기 위해 사용되는 것으로 보입니다.

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

언급URL : https://stackoverflow.com/questions/45734389/how-to-understand-the-algorithm-of-mysqls-gen-lex-hash-cc