index.  All other pages are either leaf pages or internal pages.
   Leaf pages are the pages on the lowest level of the tree.  All
   other levels consist of internal pages.  Each leaf page contains
   tuples that point to table rows.  Each internal page contains
   tuples that point to the next level down in the tree.  Typically,
   over 99% of all pages are leaf pages.  Both internal pages and leaf
   pages use the standard page format described in <xref
    linkend="storage-page-layout"/>.
  </para>
  <para>
   New leaf pages are added to a B-Tree index when an existing leaf
   page cannot fit an incoming tuple.  A <firstterm>page
    split</firstterm> operation makes room for items that originally
   belonged on the overflowing page by moving a portion of the items
   to a new page.  Page splits must also insert a new
   <firstterm>downlink</firstterm> to the new page in the parent page,
   which may cause the parent to split in turn.  Page splits
   <quote>cascade upwards</quote> in a recursive fashion.  When the
   root page finally cannot fit a new downlink, a <firstterm>root page
    split</firstterm> operation takes place.  This adds a new level to
   the tree structure by creating a new root page that is one level
   above the original root page.
  </para>
 </sect3>

 <sect3 id="btree-deletion">
  <title>Bottom-up Index Deletion</title>
  <para>
   B-Tree indexes are not directly aware that under MVCC, there might
   be multiple extant versions of the same logical table row; to an
   index, each tuple is an independent object that needs its own index
   entry.  <quote>Version churn</quote> tuples may sometimes
   accumulate and adversely affect query latency and throughput.  This
   typically occurs with <command>UPDATE</command>-heavy workloads
   where most individual updates cannot apply the
   <link linkend="storage-hot"><acronym>HOT</acronym> optimization.</link>
   Changing the value of only
   one column covered by one index during an <command>UPDATE</command>
   <emphasis>always</emphasis> necessitates a new set of index tuples
   &mdash; one for <emphasis>each and every</emphasis> index on the
   table.  Note in particular that this includes indexes that were not
   <quote>logically modified</quote> by the <command>UPDATE</command>.
   All indexes will need a successor physical index tuple that points
   to the latest version in the table.  Each new tuple within each
   index will generally need to coexist with the original
   <quote>updated</quote> tuple for a short period of time (typically
   until shortly after the <command>UPDATE</command> transaction
   commits).
  </para>
  <para>
   B-Tree indexes incrementally delete version churn index tuples by
   performing <firstterm>bottom-up index deletion</firstterm> passes.
   Each deletion pass is triggered in reaction to an anticipated
   <quote>version churn page split</quote>.  This only happens with
   indexes that are not logically modified by
   <command>UPDATE</command> statements, where concentrated build up
   of obsolete versions in particular pages would occur otherwise.  A
   page split will usually be avoided, though it's possible that
   certain implementation-level heuristics will fail to identify and
   delete even one garbage index tuple (in which case a page split or
   deduplication pass resolves the issue of an incoming new tuple not
   fitting on a leaf page).  The worst-case number of versions that
   any index scan must traverse (for any single logical row) is an
   important contributor to overall system responsiveness and
   throughput.  A bottom-up index deletion pass targets suspected
   garbage tuples in a single leaf page based on
   <emphasis>qualitative</emphasis> distinctions involving logical
   rows and versions.  This contrasts with the <quote>top-down</quote>
   index cleanup performed by autovacuum workers, which is triggered
   when certain <emphasis>quantitative</emphasis> table-level
   thresholds are exceeded (see <xref