{"id":4224,"date":"2013-01-25T20:24:05","date_gmt":"2013-01-25T12:24:05","guid":{"rendered":"http:\/\/www.orczhou.com\/?p=4224"},"modified":"2013-01-25T20:24:05","modified_gmt":"2013-01-25T12:24:05","slug":"mysql-source-code-range-optimize-data-structure-again","status":"publish","type":"post","link":"https:\/\/www.orczhou.com\/index.php\/2013\/01\/mysql-source-code-range-optimize-data-structure-again\/","title":{"rendered":"MySQL\u6e90\u7801\uff1aRange\u8bbf\u95ee\u65b9\u5f0f\u76f8\u5173\u7684\u6570\u636e\u7ed3\u6784&#8211;\u7eed"},"content":{"rendered":"<p><a href=\"http:\/\/www.orczhou.com\/index.php\/2012\/11\/mysql-source-code-range-optimize-data-structure\/\" target=\"_blank\">\u524d\u6587<\/a>\u7740\u91cd\u4ecb\u7ecd\u4e86MySQL\u7684WHERE\u6761\u4ef6\u5982\u4f55\u9488\u5bf9<strong>\u5355\u4e2a<\/strong>\u7d22\u5f15\u6784\u9020\u5bf9\u5e94\u7684SEL_ARG\u7ed3\u6784\uff0c\u672c\u6587\u662f\u4e00\u4e2a\u8865\u5145\uff0c\u5c06\u7b80\u5355\u4ecb\u7ecd\u591a\u4e2a\u7d22\u5f15\u5bf9\u5e94\u7684SEL_TREE\u7ed3\u6784\u3002<\/p>\n<p>\u5bf9\u4e8e\u4e00\u4e2a\u5b8c\u6574\u7684WHERE\u6761\u4ef6\uff0cMySQL\u4f1a\u904d\u5386\u6240\u6709\u53ef\u4ee5\u4f7f\u7528\u7684\u7d22\u5f15\uff0c\u9010\u4e00\u6784\u9020\u5176\u5bf9\u5e94\u7684SEL_ARG\u7ed3\u6784\uff0c\u6240\u6709\u7684SEL_ARG\u7ed3\u6784\u4ee5\u6307\u9488\u6570\u7ec4\u7684\u5f62\u5f0f\u5b58\u653e\u5728SEL_TREE->keys\u4e2d\u3002\u5982\u679c\u5bf9\u5e94\u7d22\u5f15\u65e0\u6cd5\u6784\u9020SEL_ARG\uff0c\u90a3\u4e48\u5bf9\u5e94\u7684\u6307\u9488\u4e3a\u7a7a\u3002<!--more--><\/p>\n<pre><blockquote>class SEL_TREE :public Sql_alloc\r\n{\r\n...\r\n  SEL_ARG *keys[MAX_KEY];\r\n...\r\n};<\/blockquote><\/pre>\n<p>gdb\u6253\u5370\u5bf9\u5e94\u7684\u7ed3\u6784\uff1a<\/p>\n<pre><blockquote>(gdb) p $1\r\n$2 = (SEL_TREE *) 0x7f59c4038348\r\n(gdb) p *$1\r\n$3 = {\r\n...\r\n  keys = {0x0, 0x7f59c4038598, 0x0 <repeats 62 times>}, \r\n...\r\n}\r\n<\/blockquote><\/pre>\n<p>SEL_TREE\u662f\u4e00\u4e2a\u6570\u7ec4\uff0c\u4f46\u5982\u679c\u50cf\u4ed6\u7684\u540d\u5b57\uff0c\u4ed6\u5982\u679c\u771f\u662f\u4e00\u68f5\u6811\u7684\u8bdd\uff0c\u90a3\u4e48\u5c06\u662f\u5982\u4e0b\u7ed3\u6784\uff1a<\/p>\n<pre><blockquote style=\"line-height:100%;\">                                          [ key1 part1 ]        [ key1 part2 ]            [ key1 part3 ]\r\n            -\\ \/-                                        $                            $       \r\n              -                         \/ SEL_ARG(-\u221e, 1) $ ===>  SEL_ARG  [5,5] ===>  $ SEL_ARG [10,10]     \r\n              |......                   |        |^      $                            $        |^     \r\n              |                         |    next||      $                            $    next|| \r\n        ......|                         |        ||prev  $                            $        ||prev \r\n    0x0       |              \/--------->|        ||      $                            $        v      \r\n      \\       |              |          |        ||      $                            $ SEL_ARG [12,12]\r\n       \\------|              |          |        ||      $                            $      \r\n        [key4]|              |          |        v|      $                            $      \r\n              |              |          | SEL_ARG [2, 2] $=== next_key_part =====|    $      \r\n              |      [link of SEL_ARG]  |        |^      $                       |    $      \r\n              |         \/               |    next||      $                       |    $      \r\n              |--------\/                |        ||prev  $                       |===>$ SEL_ARG[11,11]\r\n              | [key3]                  |        v|      $                       |    $         |^     \r\n              |                         \\ SEL_ARG [3, 3] $=== next_key_part =====|    $     next|| \r\n              |                                          $                            $         ||prev \r\n              |                                          $                            $         v|     \r\n              |                                                                      SEL_ARG[14,14]\r\n  [SEL_ARG]   |     *************************\r\n      \\       |     * structure of SEL_TREE *\r\n       \\------|     *************************\r\n        [key2]|\r\n              |      \r\n              |                           [ key1 part1 ] \r\n              |                         \/ SEL_ARG (-\u221e,2]  $            SEL_ARG [3,5)           \r\n              |                         |        |^       $                \/\\ Black\r\n              |                         |    next||       $               \/  \\   \r\n              |      [link of SEL_ARG]  |        ||prev   $              \/    \\      \r\n              |         \/     |         |        v|       $ SEL_ARG (-\u221e,2]   SEL_ARG (10,\u221e) \r\n              |--------\/      |         | SEL_ARG [3,5)   $         Red           Red    \r\n              | [key1]        |-------->|        |^       $      \r\n              |                         |    next||       $      \r\n              |                         |        ||prev   $      \r\n          SEL_TREE                      |        v|       $      \r\n                                        \\ SEL_ARG (10,\u221e)  $\r\n                                                          $<\/blockquote><\/pre>\n<p>\uff08<a href=\"http:\/\/www.flickr.com\/photos\/26825745@N06\/8401758300\/in\/photostream\/lightbox\/\" target=\"_blank\">\u5927\u56fe<\/a>\uff09<\/p>\n<p>That&#8217;s all. \u672c\u6587\u8f83\u4e3a\u7b80\u5355\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u524d\u6587\u7740\u91cd\u4ecb\u7ecd\u4e86MySQL\u7684WHERE\u6761\u4ef6\u5982\u4f55\u9488\u5bf9\u5355\u4e2a\u7d22\u5f15\u6784\u9020\u5bf9\u5e94\u7684SEL_ARG\u7ed3\u6784\uff0c\u672c\u6587\u662f\u4e00\u4e2a\u8865\u5145\uff0c\u5c06\u7b80\u5355\u4ecb\u7ecd\u591a\u4e2a\u7d22\u5f15\u5bf9\u5e94\u7684SEL_TREE\u7ed3\u6784\u3002 \u5bf9\u4e8e\u4e00\u4e2a\u5b8c\u6574\u7684WHERE\u6761\u4ef6\uff0cMySQL\u4f1a\u904d\u5386\u6240\u6709\u53ef\u4ee5\u4f7f\u7528\u7684\u7d22\u5f15\uff0c\u9010\u4e00\u6784\u9020\u5176\u5bf9\u5e94\u7684SEL_ARG\u7ed3\u6784\uff0c\u6240\u6709\u7684SEL_ARG\u7ed3\u6784\u4ee5\u6307\u9488\u6570\u7ec4\u7684\u5f62\u5f0f\u5b58\u653e\u5728SEL_TREE->keys\u4e2d\u3002\u5982\u679c\u5bf9\u5e94\u7d22\u5f15\u65e0\u6cd5\u6784\u9020SEL_ARG\uff0c\u90a3\u4e48\u5bf9\u5e94\u7684\u6307\u9488\u4e3a\u7a7a\u3002<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_eb_attr":"","inline_featured_image":false,"_tocer_settings":[],"footnotes":""},"categories":[6],"tags":[],"class_list":["post-4224","post","type-post","status-publish","format-standard","hentry","category-mysql"],"_links":{"self":[{"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/posts\/4224","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/comments?post=4224"}],"version-history":[{"count":15,"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/posts\/4224\/revisions"}],"predecessor-version":[{"id":4259,"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/posts\/4224\/revisions\/4259"}],"wp:attachment":[{"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/media?parent=4224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/categories?post=4224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.orczhou.com\/index.php\/wp-json\/wp\/v2\/tags?post=4224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}