<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="X-UA-Compatible" content="IE=Edge" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Indices — Bazaar 2.7.0 documentation</title>
<link rel="stylesheet" href="_static/classic.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="_static/language_data.js"></script>
<link rel="shortcut icon" href="_static/bzr.ico"/>
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="Inventories" href="inventory.html" />
<link rel="prev" title="Overview" href="groupcompress-design.html" />
<link rel="stylesheet" href="_static/bzr-doc.css" type="text/css" />
</head><body>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="inventory.html" title="Inventories"
accesskey="N">next</a></li>
<li class="right" >
<a href="groupcompress-design.html" title="Overview"
accesskey="P">previous</a> |</li>
<li><a href="http://bazaar.canonical.com/">
<img src="_static/bzr icon 16.png" /> Home</a> | </li>
<a href="http://doc.bazaar.canonical.com/en/">Documentation</a> | </li>
<li class="nav-item nav-item-0"><a href="index.html">Developer Document Catalog (2.7.0)</a> »</li>
<li class="nav-item nav-item-1"><a href="specifications.html" accesskey="U">Specifications</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="indices">
<h1><a class="toc-backref" href="#id1">Indices</a><a class="headerlink" href="#indices" title="Permalink to this headline">¶</a></h1>
<div class="section" id="status">
<h2><a class="toc-backref" href="#id2">Status</a><a class="headerlink" href="#status" title="Permalink to this headline">¶</a></h2>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field-odd field"><th class="field-name">Date:</th><td class="field-body">2007-07-14</td>
</tr>
</tbody>
</table>
<p>This document describes the indexing facilities within bzrlib.</p>
<div class="contents topic" id="contents">
<p class="topic-title first">Contents</p>
<ul class="simple">
<li><a class="reference internal" href="#indices" id="id1">Indices</a><ul>
<li><a class="reference internal" href="#status" id="id2">Status</a></li>
<li><a class="reference internal" href="#motivation" id="id3">Motivation</a></li>
<li><a class="reference internal" href="#terminology" id="id4">Terminology</a></li>
<li><a class="reference internal" href="#overview" id="id5">Overview</a></li>
<li><a class="reference internal" href="#general-index-api" id="id6">General Index API</a><ul>
<li><a class="reference internal" href="#services" id="id7">Services</a><ul>
<li><a class="reference internal" href="#build-index" id="id8">Build index</a></li>
<li><a class="reference internal" href="#retrieve-entries-from-the-index" id="id9">Retrieve entries from the index</a></li>
<li><a class="reference internal" href="#merging-of-indices" id="id10">Merging of indices</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#index-implementations" id="id11">Index implementations</a><ul>
<li><a class="reference internal" href="#graphindex" id="id12">GraphIndex</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<div class="section" id="motivation">
<h2><a class="toc-backref" href="#id3">Motivation</a><a class="headerlink" href="#motivation" title="Permalink to this headline">¶</a></h2>
<p>To provide a clean concept of index that can be reused by different
components within the codebase rather than being rewritten every time
by different components.</p>
</div>
<div class="section" id="terminology">
<h2><a class="toc-backref" href="#id4">Terminology</a><a class="headerlink" href="#terminology" title="Permalink to this headline">¶</a></h2>
<p>An <strong>index</strong> is a dictionary mapping opaque keys to opaque values.
Different index types may allow some of the value data to be interpreted
by the index. For example the <code class="docutils literal notranslate"><span class="pre">GraphIndex</span></code> index stores a graph between
keys as part of the index.</p>
</div>
<div class="section" id="overview">
<h2><a class="toc-backref" href="#id5">Overview</a><a class="headerlink" href="#overview" title="Permalink to this headline">¶</a></h2>
<p>bzr is moving to a write-once model for repository storage in order to
achieve lock-free repositories eventually. In order to support this, we are
making our new index classes <strong>immutable</strong>. That is, one creates a new
index in a single operation, and after that it is read only. To combine
two indices a <code class="docutils literal notranslate"><span class="pre">Combined*</span></code> index may be used, or an <strong>index merge</strong> may
be performed by reading the entire value of two (or more) indices and
writing them into a new index.</p>
</div>
<div class="section" id="general-index-api">
<h2><a class="toc-backref" href="#id6">General Index API</a><a class="headerlink" href="#general-index-api" title="Permalink to this headline">¶</a></h2>
<p>We may end up with multiple different Index types (e.g. GraphIndex,
Index, WhackyIndex). Even though these may require different method
signatures to operate would strive to keep the signatures and return
values as similar as possible. e.g.:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">GraphIndexBuilder</span> <span class="o">-</span> <span class="n">add_node</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span> <span class="n">references</span><span class="p">)</span>
<span class="n">IndexBuilder</span> <span class="o">-</span> <span class="n">add_node</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">)</span>
<span class="n">WhackyIndexBuilder</span> <span class="o">-</span> <span class="n">add_node</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span> <span class="n">whackiness</span><span class="p">)</span>
</pre></div>
</div>
<p>as opposed to something quite different like:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">node</span> <span class="o">=</span> <span class="n">IncrementalBuilder</span><span class="o">.</span><span class="n">get_node</span><span class="p">()</span>
<span class="n">node</span><span class="o">.</span><span class="n">key</span> <span class="o">=</span> <span class="s1">'foo'</span>
<span class="n">node</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="s1">'bar'</span>
</pre></div>
</div>
<div class="section" id="services">
<h3><a class="toc-backref" href="#id7">Services</a><a class="headerlink" href="#services" title="Permalink to this headline">¶</a></h3>
<p>An initial implementation of indexing can probably get away with a small
number of primitives. Assuming we have write once index files:</p>
<div class="section" id="build-index">
<h4><a class="toc-backref" href="#id8">Build index</a><a class="headerlink" href="#build-index" title="Permalink to this headline">¶</a></h4>
<p>This should be done by creating an <code class="docutils literal notranslate"><span class="pre">IndexBuilder</span></code> and then calling
<code class="docutils literal notranslate"><span class="pre">insert(key,</span> <span class="pre">value)</span></code> many times. (Indices that support sorting,
topological sorting etc, will want specialised insert methods).</p>
<p>When the keys have all been added, a <code class="docutils literal notranslate"><span class="pre">finish</span></code> method should be called,
which will return a file stream to read the index data from.</p>
</div>
<div class="section" id="retrieve-entries-from-the-index">
<h4><a class="toc-backref" href="#id9">Retrieve entries from the index</a><a class="headerlink" href="#retrieve-entries-from-the-index" title="Permalink to this headline">¶</a></h4>
<p>This should allow random access to the index using readv, so we probably
want to open the index on a <code class="docutils literal notranslate"><span class="pre">Transport</span></code>, then use <code class="docutils literal notranslate"><span class="pre">iter_entries(keys)</span></code>,
which can return an iterator that yields <code class="docutils literal notranslate"><span class="pre">(key,</span> <span class="pre">value)</span></code> pairs in
whatever order makes sense for the index.</p>
</div>
<div class="section" id="merging-of-indices">
<h4><a class="toc-backref" href="#id10">Merging of indices</a><a class="headerlink" href="#merging-of-indices" title="Permalink to this headline">¶</a></h4>
<p>Merging of N indices requires a concordance of the keys of the index. So
we should offer a <code class="docutils literal notranslate"><span class="pre">iter_all_entries</span></code> call that has the same return type
as the <code class="docutils literal notranslate"><span class="pre">iter_entries</span></code> call.</p>
</div>
</div>
</div>
<div class="section" id="index-implementations">
<h2><a class="toc-backref" href="#id11">Index implementations</a><a class="headerlink" href="#index-implementations" title="Permalink to this headline">¶</a></h2>
<div class="section" id="graphindex">
<h3><a class="toc-backref" href="#id12">GraphIndex</a><a class="headerlink" href="#graphindex" title="Permalink to this headline">¶</a></h3>
<p><code class="docutils literal notranslate"><span class="pre">GraphIndex</span></code> supports graph based lookups. While currently unoptimised
for reading, the index is quite space efficient at storing the revision
graph index for bzr. The <code class="docutils literal notranslate"><span class="pre">GraphIndexBuilder</span></code> may be used to create one
of these indices by calling <code class="docutils literal notranslate"><span class="pre">add_node</span></code> until all nodes are added, then
<code class="docutils literal notranslate"><span class="pre">finish</span></code> to obtain a file stream containing the index data. Multiple
indices may be queried using the <code class="docutils literal notranslate"><span class="pre">CombinedGraphIndex</span></code> class.</p>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">Indices</a><ul>
<li><a class="reference internal" href="#status">Status</a></li>
<li><a class="reference internal" href="#motivation">Motivation</a></li>
<li><a class="reference internal" href="#terminology">Terminology</a></li>
<li><a class="reference internal" href="#overview">Overview</a></li>
<li><a class="reference internal" href="#general-index-api">General Index API</a><ul>
<li><a class="reference internal" href="#services">Services</a><ul>
<li><a class="reference internal" href="#build-index">Build index</a></li>
<li><a class="reference internal" href="#retrieve-entries-from-the-index">Retrieve entries from the index</a></li>
<li><a class="reference internal" href="#merging-of-indices">Merging of indices</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#index-implementations">Index implementations</a><ul>
<li><a class="reference internal" href="#graphindex">GraphIndex</a></li>
</ul>
</li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="groupcompress-design.html"
title="previous chapter">Overview</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="inventory.html"
title="next chapter">Inventories</a></p>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/indices.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3>Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="inventory.html" title="Inventories"
>next</a></li>
<li class="right" >
<a href="groupcompress-design.html" title="Overview"
>previous</a> |</li>
<li><a href="http://bazaar.canonical.com/">
<img src="_static/bzr icon 16.png" /> Home</a> | </li>
<a href="http://doc.bazaar.canonical.com/en/">Documentation</a> | </li>
<li class="nav-item nav-item-0"><a href="index.html">Developer Document Catalog (2.7.0)</a> »</li>
<li class="nav-item nav-item-1"><a href="specifications.html" >Specifications</a> »</li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2009-2011 Canonical Ltd.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.8.4.
</div>
</body>
</html>
