<div id="docs-body">
 <div class="section">
  <div class="titlepage">
   <div>
    <div>
     <h4 class="title">
      <a name="innodb-physical-structure">
      </a>
      17.6.2.2 The Physical Structure of an InnoDB Index
     </h4>
    </div>
   </div>
  </div>
  <a class="indexterm" name="idm46045165840144">
  </a>
  <a class="indexterm" name="idm46045165838688">
  </a>
  <a class="indexterm" name="idm46045165837200">
  </a>
  <a class="indexterm" name="idm46045165835712">
  </a>
  <a class="indexterm" name="idm46045165834640">
  </a>
  <p>
   With the exception of spatial indexes,
   <code class="literal">
    InnoDB
   </code>
   indexes are
   <a class="link" href="glossary.html#glos_b_tree" title="B-tree">
    B-tree
   </a>
   data
      structures. Spatial indexes use
   <a class="link" href="glossary.html#glos_r_tree" title="R-tree">
    R-trees
   </a>
   , which are
      specialized data structures for indexing multi-dimensional data.
      Index records are stored in the leaf pages of their B-tree or
      R-tree data structure. The default size of an index page is 16KB.
      The page size is determined by the
   <a class="link" href="innodb-parameters.html#sysvar_innodb_page_size">
    <code class="literal">
     innodb_page_size
    </code>
   </a>
   setting when the
      MySQL instance is initialized. See
   <a class="xref" href="innodb-init-startup-configuration.html" title="17.8.1 InnoDB Startup Configuration">
    Section 17.8.1, “InnoDB Startup Configuration”
   </a>
   .
  </p>
  <p>
   When new records are inserted into an
   <code class="literal">
    InnoDB
   </code>
   <a class="link" href="glossary.html#glos_clustered_index" title="clustered index">
    clustered index
   </a>
   ,
   <code class="literal">
    InnoDB
   </code>
   tries to leave 1/16 of the page free for
      future insertions and updates of the index records. If index
      records are inserted in a sequential order (ascending or
      descending), the resulting index pages are about 15/16 full. If
      records are inserted in a random order, the pages are from 1/2 to
      15/16 full.
  </p>
  <p>
   <code class="literal">
    InnoDB
   </code>
   performs a bulk load when creating or
      rebuilding B-tree indexes. This method of index creation is known
      as a sorted index build. The
   <a class="link" href="innodb-parameters.html#sysvar_innodb_fill_factor">
    <code class="literal">
     innodb_fill_factor
    </code>
   </a>
   variable
      defines the percentage of space on each B-tree page that is filled
      during a sorted index build, with the remaining space reserved for
      future index growth. Sorted index builds are not supported for
      spatial indexes. For more information, see
   <a class="xref" href="sorted-index-builds.html" title="17.6.2.3 Sorted Index Builds">
    Section 17.6.2.3, “Sorted Index Builds”
   </a>
   . An
   <a class="link" href="innodb-parameters.html#sysvar_innodb_fill_factor">
    <code class="literal">
     innodb_fill_factor
    </code>
   </a>
   setting of 100
      leaves 1/16 of the space in clustered index pages free for future
      index growth.
  </p>
  <p>
   If the fill factor of an
   <code class="literal">
    InnoDB
   </code>
   index page
      drops below the
   <code class="literal">
    MERGE_THRESHOLD
   </code>
   , which is 50%
      by default if not specified,
   <code class="literal">
    InnoDB
   </code>
   tries to
      contract the index tree to free the page. The
   <code class="literal">
    MERGE_THRESHOLD
   </code>
   setting applies to both B-tree
      and R-tree indexes. For more information, see
   <a class="xref" href="index-page-merge-threshold.html" title="17.8.11 Configuring the Merge Threshold for Index Pages">
    Section 17.8.11, “Configuring the Merge Threshold for Index Pages”
   </a>
   .
  </p>
 </div>
 <br/>
</div>
