/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to doc/developers/indices.txt

  • Committer: Martin Pool
  • Date: 2005-06-28 03:02:31 UTC
  • Revision ID: mbp@sourcefrog.net-20050628030231-d311e4ebcd467ef4
Merge John's import-speedup branch:

                                                                                         
  777 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:32 -0500
      revision-id: john@arbash-meinel.com-20050627032031-e82a50db3863b18e
      bzr selftest was not using the correct bzr

  776 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:22 -0500
      revision-id: john@arbash-meinel.com-20050627032021-c9f21fde989ddaee
      Add was using an old mutter

  775 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:02:33 -0500
      revision-id: john@arbash-meinel.com-20050627030233-9165cfe98fc63298
      Cleaned up to be less different

  774 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:54:53 -0500
      revision-id: john@arbash-meinel.com-20050627025452-4260d0e744edef43
      Allow BZR_PLUGIN_PATH='' to negate plugin loading.

  773 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:49:34 -0500
      revision-id: john@arbash-meinel.com-20050627024933-b7158f67b7b9eae5
      Finished the previous cleanup (allowing load_plugins to be called twice)

  772 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:45:08 -0500
      revision-id: john@arbash-meinel.com-20050627024508-723b1df510d196fc
      Work on making the tests pass. versioning.py is calling run_cmd directly, but plugins have been loaded.

  771 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:32:29 -0500
      revision-id: john@arbash-meinel.com-20050627023228-79972744d7c53e15
      Got it down a little bit more by removing import of tree and inventory.

  770 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:26:05 -0500
      revision-id: john@arbash-meinel.com-20050627022604-350b9773ef622f95
      Reducing the number of import from bzrlib/__init__.py and bzrlib/branch.py

  769 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:32:25 -0500
      revision-id: john@arbash-meinel.com-20050627013225-32dd044f10d23948
      Updated revision.py and xml.py to include SubElement.

  768 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:56 -0500
      revision-id: john@arbash-meinel.com-20050627010356-ee66919e1c377faf
      Minor typo

  767 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:13 -0500
      revision-id: john@arbash-meinel.com-20050627010312-40d024007eb85051
      Caching the import

  766 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:51:47 -0500
      revision-id: john@arbash-meinel.com-20050627005147-5281c99e48ed1834
      Created wrapper functions for lazy import of ElementTree

  765 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:46:37 -0500
      revision-id: john@arbash-meinel.com-20050627004636-bf432902004a94c5
      Removed all of the test imports of cElementTree

  764 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:43:59 -0500
      revision-id: john@arbash-meinel.com-20050627004358-d137fbe9570dd71b
      Trying to make bzr startup faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/indices.txt
1
 
=======
2
 
Indices
3
 
=======
4
 
 
5
 
Status
6
 
======
7
 
 
8
 
:Date: 2007-07-14
9
 
 
10
 
This document describes the indexing facilities within bzrlib.
11
 
 
12
 
 
13
 
.. contents::
14
 
 
15
 
 
16
 
Motivation
17
 
==========
18
 
 
19
 
To provide a clean concept of index that can be reused by different
20
 
components within the codebase rather than being rewritten every time
21
 
by different components.
22
 
 
23
 
 
24
 
Terminology
25
 
===========
26
 
 
27
 
An **index** is a dictionary mapping opaque keys to opaque values.
28
 
Different index types may allow some of the value data to be interpreted
29
 
by the index. For example the ``GraphIndex`` index stores a graph between
30
 
keys as part of the index.
31
 
 
32
 
 
33
 
Overview
34
 
========
35
 
 
36
 
bzr is moving to a write-once model for repository storage in order to
37
 
achieve lock-free repositories eventually. In order to support this, we are
38
 
making our new index classes **immutable**. That is, one creates a new
39
 
index in a single operation, and after that it is read only. To combine
40
 
two indices a ``Combined*`` index may be used, or an **index merge** may
41
 
be performed by reading the entire value of two (or more) indices and
42
 
writing them into a new index.
43
 
 
44
 
General Index API
45
 
=================
46
 
 
47
 
We may end up with multiple different Index types (e.g. GraphIndex,
48
 
Index, WhackyIndex). Even though these may require different method
49
 
signatures to operate would strive to keep the signatures and return
50
 
values as similar as possible. e.g.::
51
 
 
52
 
    GraphIndexBuilder - add_node(key, value, references)
53
 
    IndexBuilder - add_node(key, value)
54
 
    WhackyIndexBuilder - add_node(key, value, whackiness)
55
 
 
56
 
as opposed to something quite different like::
57
 
 
58
 
    node = IncrementalBuilder.get_node()
59
 
    node.key = 'foo'
60
 
    node.value = 'bar'
61
 
 
62
 
Services
63
 
--------
64
 
 
65
 
An initial implementation of indexing can probably get away with a small
66
 
number of primitives. Assuming we have write once index files:
67
 
 
68
 
Build index
69
 
~~~~~~~~~~~
70
 
 
71
 
This should be done by creating an ``IndexBuilder`` and then calling
72
 
``insert(key, value)`` many times. (Indices that support sorting,
73
 
topological sorting etc, will want specialised insert methods).
74
 
 
75
 
When the keys have all been added, a ``finish`` method should be called,
76
 
which will return a file stream to read the index data from.
77
 
 
78
 
Retrieve entries from the index
79
 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
80
 
 
81
 
This should allow random access to the index using readv, so we probably
82
 
want to open the index on a ``Transport``, then use ``iter_entries(keys)``,
83
 
which can return an iterator that yields ``(key, value)`` pairs in
84
 
whatever order makes sense for the index.
85
 
 
86
 
Merging of indices
87
 
~~~~~~~~~~~~~~~~~~
88
 
 
89
 
Merging of N indices requires a concordance of the keys of the index. So
90
 
we should offer a ``iter_all_entries`` call that has the same return type
91
 
as the ``iter_entries`` call.
92
 
 
93
 
Index implementations
94
 
=====================
95
 
 
96
 
GraphIndex
97
 
----------
98
 
 
99
 
``GraphIndex`` supports graph based lookups. While currently unoptimised
100
 
for reading, the index is quite space efficient at storing the revision
101
 
graph index for bzr. The ``GraphIndexBuilder`` may be used to create one
102
 
of these indices by calling ``add_node`` until all nodes are added, then
103
 
``finish`` to obtain a file stream containing the index data. Multiple
104
 
indices may be queried using the ``CombinedGraphIndex`` class.
105
 
 
106
 
 
107
 
 
108
 
 
109
 
..
110
 
   vim: ft=rst tw=74 ai
111