← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to doc/developers/indices.txt

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

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