<div id="docs-body">
 <div class="section">
  <div class="titlepage">
   <div>
    <div>
     <h3 class="title">
      <a name="index-btree-hash">
      </a>
      10.3.9 Comparison of B-Tree and Hash Indexes
     </h3>
    </div>
   </div>
  </div>
  <a class="indexterm" name="idm46045227233648">
  </a>
  <a class="indexterm" name="idm46045227232608">
  </a>
  <p>
   Understanding the B-tree and hash data structures can help
        predict how different queries perform on different storage
        engines that use these data structures in their indexes,
        particularly for the
   <code class="literal">
    MEMORY
   </code>
   storage engine
        that lets you choose B-tree or hash indexes.
  </p>
  <div class="itemizedlist">
   <ul class="itemizedlist" style="list-style-type: disc; ">
    <li class="listitem">
     <p>
      <a class="xref" href="index-btree-hash.html#btree-index-characteristics" title="B-Tree Index Characteristics">
       B-Tree Index Characteristics
      </a>
     </p>
    </li>
    <li class="listitem">
     <p>
      <a class="xref" href="index-btree-hash.html#hash-index-characteristics" title="Hash Index Characteristics">
       Hash Index Characteristics
      </a>
     </p>
    </li>
   </ul>
  </div>
  <div class="simplesect">
   <div class="titlepage">
    <div>
     <div class="simple">
      <h4 class="title">
       <a name="btree-index-characteristics">
       </a>
       B-Tree Index Characteristics
      </h4>
     </div>
    </div>
   </div>
   <a class="indexterm" name="idm46045227226576">
   </a>
   <a class="indexterm" name="idm46045227225088">
   </a>
   <a class="indexterm" name="idm46045227223600">
   </a>
   <a class="indexterm" name="idm46045227222112">
   </a>
   <p>
    A B-tree index can be used for column comparisons in
          expressions that use the
    <a class="link" href="comparison-operators.html#operator_equal">
     <code class="literal">
      =
     </code>
    </a>
    ,
    <a class="link" href="comparison-operators.html#operator_greater-than">
     <code class="literal">
      &gt;
     </code>
    </a>
    ,
    <a class="link" href="comparison-operators.html#operator_greater-than-or-equal">
     <code class="literal">
      &gt;=
     </code>
    </a>
    ,
    <a class="link" href="comparison-operators.html#operator_less-than">
     <code class="literal">
      &lt;
     </code>
    </a>
    ,
    <a class="link" href="comparison-operators.html#operator_less-than-or-equal">
     <code class="literal">
      &lt;=
     </code>
    </a>
    ,
          or
    <a class="link" href="comparison-operators.html#operator_between">
     <code class="literal">
      BETWEEN
     </code>
    </a>
    operators. The index
          also can be used for
    <a class="link" href="string-comparison-functions.html#operator_like">
     <code class="literal">
      LIKE
     </code>
    </a>
    comparisons if the argument to
    <a class="link" href="string-comparison-functions.html#operator_like">
     <code class="literal">
      LIKE
     </code>
    </a>
    is a constant string that
          does not start with a wildcard character. For example, the
          following
    <a class="link" href="select.html" title="15.2.13 SELECT Statement">
     <code class="literal">
      SELECT
     </code>
    </a>
    statements use
          indexes:
   </p>
   <div class="copytoclipboard-wrapper">
    <pre class="programlisting language-sql"><div class="docs-select-all right" id="sa19789403"><div class="copy-help left">Press ⌘+C to copy</div> <div class="right"><button class="clipboard-btn" title="Copy to Clipboard"><span class="icon-clipboard"></span></button></div></div><code class="language-sql"><span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <em class="replaceable">tbl_name</em> <span class="token keyword">WHERE</span> <em class="replaceable">key_col</em> <span class="token operator">LIKE</span> <span class="token string">'Patrick%'</span><span class="token punctuation">;</span>
<span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <em class="replaceable">tbl_name</em> <span class="token keyword">WHERE</span> <em class="replaceable">key_col</em> <span class="token operator">LIKE</span> <span class="token string">'Pat%_ck%'</span><span class="token punctuation">;</span></code></pre>
   </div>
   <p>
    In the first statement, only rows with
    <code class="literal">
     'Patrick'
          &lt;=
     <em class="replaceable">
      <code>
       key_col
      </code>
     </em>
     &lt;
          'Patricl'
    </code>
    are considered. In the second statement,
          only rows with
    <code class="literal">
     'Pat' &lt;=
     <em class="replaceable">
      <code>
       key_col
      </code>
     </em>
     &lt; 'Pau'
    </code>
    are
          considered.
   </p>
   <p>
    The following
    <a class="link" href="select.html" title="15.2.13 SELECT Statement">
     <code class="literal">
      SELECT
     </code>
    </a>
    statements
          do not use indexes:
   </p>
   <div class="copytoclipboard-wrapper">
    <pre class="programlisting language-sql"><div class="docs-select-all right" id="sa31302888"><div class="copy-help left">Press ⌘+C to copy</div> <div class="right"><button class="clipboard-btn" title="Copy to Clipboard"><span class="icon-clipboard"></span></button></div></div><code class="language-sql"><span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <em class="replaceable">tbl_name</em> <span class="token keyword">WHERE</span> <em class="replaceable">key_col</em> <span class="token operator">LIKE</span> <span class="token string">'%Patrick%'</span><span class="token punctuation">;</span>
<span class="token keyword">SELECT</span> <span class="token operator">*</span> <span class="token keyword">FROM</span> <em class="replaceable">tbl_name</em> <span class="token keyword">WHERE</span> <em class="replaceable">key_col</em> <span class="token operator">LIKE</span> <em class="replaceable">other_col</em><span class="token punctuation">;</span></code></pre>
   </div>
   <p>
    In the first statement, the
    <a class="link" href="string-comparison-functions.html#operator_like">
     <code class="literal">
      LIKE
     </code>
    </a>
    value begins with a wildcard character. In the second
          statement, the
    <a class="link" href="string-comparison-functions.html#operator_like">
     <code class="literal">
      LIKE
     </code>
    </a>
    value is not
          a constant.
   </p>
   <p>
    If you use
    <code class="literal">
     ... LIKE
          '%
     <em class="replaceable">
      <code>
       string
      </code>
     </em>
     %'
    </code>
    and
    <em class="replaceable">
     <code>
      string
     </code>
    </em>
    is longer than three
          characters, MySQL uses the
    <span class="firstterm">
     Turbo
          Boyer-Moore algorithm
    </span>
    to initialize the pattern for
          the string and then uses this pattern to perform the search
          more quickly.
   </p>
   <a class="indexterm" name="idm46045227192320">
   </a>
   <a class="indexterm" name="idm46045227190832">
   </a>
   <p>
    A search using
    <code class="literal">
     <em class="replaceable">
      <code>
       col_name
      </code>
     </em>
     IS
          NULL
    </code>
    employs indexes if
    <em class="replaceable">
     <code>
      col_name
     </code>
    </em>
    is indexed.
   </p>
   <p>
    Any index that does not span all
    <a class="link" href="logical-operators.html#operator_and">
     <code class="literal">
      AND
     </code>
    </a>
    levels in the
    <code class="literal">
     WHERE
    </code>
    clause is not used to optimize the
          query. In other words, to be able to use an index, a prefix of
          the index must be used in every
    <a class="link" href="logical-operators.html#operator_and">
     <code class="literal">
      AND
     </code>
    </a>
    group.
   </p>
   <p>
    The following
    <code class="literal">
     WHERE
    </code>
    clauses use indexes:
   </p>
   <div class="copytoclipboard-wrapper">
    <pre class="programlisting language-sql"><div class="docs-select-all right" id="sa61121285"><div class="copy-help left">Press ⌘+C to copy</div> <div class="right"><button class="clipboard-btn" title="Copy to Clipboard"><span class="icon-clipboard"></span></button></div></div><code class="language-sql"><span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <em class="replaceable">index_part1</em><span class="token operator">=</span><span class="token number">1</span> <span class="token operator">AND</span> <em class="replaceable">index_part2</em><span class="token operator">=</span><span class="token number">2</span> <span class="token operator">AND</span> <em class="replaceable">other_column</em><span class="token operator">=</span><span class="token number">3</span>

    <span class="token comment" spellcheck="true">/* <em class="replaceable">index</em> = 1 OR <em class="replaceable">index</em> = 2 */</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <span class="token keyword"><em class="replaceable">index</em></span><span class="token operator">=</span><span class="token number">1</span> <span class="token operator">OR</span> A<span class="token operator">=</span><span class="token number">10</span> <span class="token operator">AND</span> <span class="token keyword"><em class="replaceable">index</em></span><span class="token operator">=</span><span class="token number">2</span>

    <span class="token comment" spellcheck="true">/* optimized like "<em class="replaceable">index_part1</em>='hello'" */</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <em class="replaceable">index_part1</em><span class="token operator">=</span><span class="token string">'hello'</span> <span class="token operator">AND</span> <em class="replaceable">index_part3</em><span class="token operator">=</span><span class="token number">5</span>

    <span class="token comment" spellcheck="true">/* Can use index on <em class="replaceable">index1</em> but not on <em class="replaceable">index2</em> or <em class="replaceable">index3</em> */</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <em class="replaceable">index1</em><span class="token operator">=</span><span class="token number">1</span> <span class="token operator">AND</span> <em class="replaceable">index2</em><span class="token operator">=</span><span class="token number">2</span> <span class="token operator">OR</span> <em class="replaceable">index1</em><span class="token operator">=</span><span class="token number">3</span> <span class="token operator">AND</span> <em class="replaceable">index3</em><span class="token operator">=</span><span class="token number">3</span><span class="token punctuation">;</span></code></pre>
   </div>
   <p>
    These
    <code class="literal">
     WHERE
    </code>
    clauses do
    <span class="emphasis">
     <em>
      not
     </em>
    </span>
    use indexes:
   </p>
   <div class="copytoclipboard-wrapper">
    <pre class="programlisting language-sql"><div class="docs-select-all right" id="sa53019683"><div class="copy-help left">Press ⌘+C to copy</div> <div class="right"><button class="clipboard-btn" title="Copy to Clipboard"><span class="icon-clipboard"></span></button></div></div><code class="language-sql">    <span class="token comment" spellcheck="true">/* <em class="replaceable">index_part1</em> is not used */</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <em class="replaceable">index_part2</em><span class="token operator">=</span><span class="token number">1</span> <span class="token operator">AND</span> <em class="replaceable">index_part3</em><span class="token operator">=</span><span class="token number">2</span>

    <span class="token comment" spellcheck="true">/*  Index is not used in both parts of the WHERE clause  */</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <span class="token keyword"><em class="replaceable">index</em></span><span class="token operator">=</span><span class="token number">1</span> <span class="token operator">OR</span> A<span class="token operator">=</span><span class="token number">10</span>

    <span class="token comment" spellcheck="true">/* No index spans all rows  */</span>
<span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">WHERE</span> <em class="replaceable">index_part1</em><span class="token operator">=</span><span class="token number">1</span> <span class="token operator">OR</span> <em class="replaceable">index_part2</em><span class="token operator">=</span><span class="token number">10</span></code></pre>
   </div>
   <p>
    Sometimes MySQL does not use an index, even if one is
          available. One circumstance under which this occurs is when
          the optimizer estimates that using the index would require
          MySQL to access a very large percentage of the rows in the
          table. (In this case, a table scan is likely to be much faster
          because it requires fewer seeks.) However, if such a query
          uses
    <code class="literal">
     LIMIT
    </code>
    to retrieve only some of the
          rows, MySQL uses an index anyway, because it can much more
          quickly find the few rows to return in the result.
   </p>
  </div>
  <div class="simplesect">
   <div class="titlepage">
    <div>
     <div class="simple">
      <h4 class="title">
       <a name="hash-index-characteristics">
       </a>
       Hash Index Characteristics
      </h4>
     </div>
    </div>
   </div>
   <a class="indexterm" name="idm46045227165680">
   </a>
   <p>
    Hash indexes have somewhat different characteristics from
          those just discussed:
   </p>
   <div class="itemizedlist">
    <ul class="itemizedlist" style="list-style-type: disc; ">
     <li class="listitem">
      <p>
       They are used only for equality comparisons that use the
       <code class="literal">
        =
       </code>
       or
       <code class="literal">
        &lt;=&gt;
       </code>
       operators (but are
       <span class="emphasis">
        <em>
         very
        </em>
       </span>
       fast). They
              are not used for comparison operators such as
       <code class="literal">
        &lt;
       </code>
       that find a range of values.
              Systems that rely on this type of single-value lookup are
              known as
       <span class="quote">
        “
        <span class="quote">
         key-value stores
        </span>
        ”
       </span>
       ; to use MySQL for
              such applications, use hash indexes wherever possible.
      </p>
     </li>
     <li class="listitem">
      <p>
       The optimizer cannot use a hash index to speed up
       <code class="literal">
        ORDER BY
       </code>
       operations. (This type of
              index cannot be used to search for the next entry in
              order.)
      </p>
     </li>
     <li class="listitem">
      <p>
       MySQL cannot determine approximately how many rows there
              are between two values (this is used by the range
              optimizer to decide which index to use). This may affect
              some queries if you change a
       <code class="literal">
        MyISAM
       </code>
       or
       <code class="literal">
        InnoDB
       </code>
       table to a hash-indexed
       <code class="literal">
        MEMORY
       </code>
       table.
      </p>
     </li>
     <li class="listitem">
      <p>
       Only whole keys can be used to search for a row. (With a
              B-tree index, any leftmost prefix of the key can be used
              to find rows.)
      </p>
     </li>
    </ul>
   </div>
  </div>
 </div>
 <br/>
</div>
