[Zodb-checkins] CVS: ZODB3/Doc/zodb - img1.gif:1.1 about.html:1.2
contents.html:1.2 index.html:1.2 node2.html:1.2
node3.html:1.2 node5.html:1.2 node6.html:1.2 node7.html:1.2
node8.html:1.2 zeo.html:1.2 zodb.css:1.2 zodb.html:1.2
Jeremy Hylton
jeremy at zope.com
Thu May 1 17:21:16 EDT 2003
Update of /cvs-repository/ZODB3/Doc/zodb
In directory cvs.zope.org:/tmp/cvs-serv6827/zodb
Modified Files:
about.html contents.html index.html node2.html node3.html
node5.html node6.html node7.html node8.html zeo.html zodb.css
zodb.html
Added Files:
img1.gif
Log Message:
Store the generated PDF and HTML for the latest guide changes.
=== Added File ZODB3/Doc/zodb/img1.gif ===
<Binary-ish file>
=== ZODB3/Doc/zodb/about.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/about.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/about.html Thu May 1 16:21:15 2003
@@ -44,7 +44,7 @@
About this document ...</A>
</H1>
<strong>ZODB/ZEO Programming Guide</strong>,
-January 17, 2003, Release 0.04
+1 May 2003, Release 0.1
<p> This document was generated using the <a
href="http://saftsack.fs.uni-bayreuth.de/~latex2ht/">
<strong>LaTeX</strong>2<tt>HTML</tt></a> translator.
@@ -91,7 +91,7 @@
<b class="navlabel">Previous:</b> <a class="sectref" HREF="node8.html">B. GNU Free Documentation</A>
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/contents.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/contents.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/contents.html Thu May 1 16:21:15 2003
@@ -81,8 +81,8 @@
</ul>
<LI><A href="node6.html">5 Related Modules</a>
<UL>
-<LI><A href="node6.html#SECTION000610000000000000000">5.1 <tt class="module">ZODB.PersistentMapping</tt></a>
-<LI><A href="node6.html#SECTION000620000000000000000">5.2 <tt class="module">ZODB.PersistentList</tt></a>
+<LI><A href="node6.html#SECTION000610000000000000000">5.1 ZODB.PersistentMapping</a>
+<LI><A href="node6.html#SECTION000620000000000000000">5.2 ZODB.PersistentList</a>
<LI><A href="node6.html#SECTION000630000000000000000">5.3 BTrees Package</a>
</ul>
<LI><A href="node7.html">A. Resources</a>
@@ -137,7 +137,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node2.html">1 Introduction</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/index.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/index.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/index.html Thu May 1 16:21:15 2003
@@ -42,9 +42,9 @@
<center>
<h1>ZODB/ZEO Programming Guide</h1>
<p><b><font size="+2">A.M. Kuchling</font></b></p>
-<p>akuchlin at mems-exchange.org</p>
-<p><strong>Release 0.04</strong><br>
-<strong>January 17, 2003</strong></p>
+<p><span class="email">amk at amk.ca</span></p>
+<p><strong>Release 0.1</strong><br>
+<strong>1 May 2003</strong></p>
<p>
</center>
</div>
@@ -108,6 +108,9 @@
<LI><A href="node6.html#SECTION000610000000000000000">5.1 <tt class="module">ZODB.PersistentMapping</tt></a>
<LI><A href="node6.html#SECTION000620000000000000000">5.2 <tt class="module">ZODB.PersistentList</tt></a>
<LI><A href="node6.html#SECTION000630000000000000000">5.3 BTrees Package</a>
+<UL>
+<LI><A href="node6.html#SECTION000631000000000000000">5.3.1 Total Ordering and Persistence</a>
+</ul>
</ul>
<LI><A href="node7.html">A. Resources</a>
<LI><A href="node8.html">B. GNU Free Documentation License</a>
@@ -149,7 +152,7 @@
</tr></table>
<b class="navlabel">Next:</b> <a class="sectref" href="contents.html">Contents</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/node2.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/node2.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/node2.html Thu May 1 16:21:15 2003
@@ -46,11 +46,11 @@
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
-<LI><A href="#SECTION000210000000000000000">1.1 What is the ZODB?</a>
-<LI><A href="#SECTION000220000000000000000">1.2 OODBs vs. Relational DBs</a>
-<LI><A href="#SECTION000230000000000000000">1.3 What is ZEO?</a>
-<LI><A href="#SECTION000240000000000000000">1.4 About this guide</a>
-<LI><A href="#SECTION000250000000000000000">1.5 Acknowledgements</a>
+<LI><A href="node2.html#SECTION000210000000000000000">1.1 What is the ZODB?</a>
+<LI><A href="node2.html#SECTION000220000000000000000">1.2 OODBs vs. Relational DBs</a>
+<LI><A href="node2.html#SECTION000230000000000000000">1.3 What is ZEO?</a>
+<LI><A href="node2.html#SECTION000240000000000000000">1.4 About this guide</a>
+<LI><A href="node2.html#SECTION000250000000000000000">1.5 Acknowledgements</a>
</ul>
<!--End of Table of Child-Links-->
<HR>
@@ -63,7 +63,7 @@
This guide explains how to write Python programs that use the Z Object
Database (ZODB) and Zope Enterprise Objects (ZEO). The latest version
of the guide is always available at
-<a class="url" href="http://www.amk.ca/zodb/guide/">http://www.amk.ca/zodb/guide/</a>.
+<a class="url" href="http://www.zope.org/Wikis/ZODB/guide/index.html">http://www.zope.org/Wikis/ZODB/guide/index.html</a>.
<P>
@@ -267,9 +267,12 @@
mistakes we did while learning.
<P>
+The author's ZODB project is described in a paper available here,
+<a class="url" href="http://www.amk.ca/python/writing/mx-architecture/">http://www.amk.ca/python/writing/mx-architecture/</a>
+<P>
This document will always be a work in progress. If you wish to
suggest clarifications or additional topics, please send your comments to
-<span class="email">akuchlin at mems-exchange.org</span>.
+<span class="email">zodb-dev at zope.org</span>.
<P>
@@ -278,6 +281,12 @@
</H2>
<P>
+Andrew Kuchling wrote the original version of this guide, which
+provided some of the first ZODB documentation for Python programmers.
+His initial version has been updated over time by Jeremy Hylton and
+Tim Peters.
+
+<P>
I'd like to thank the people who've pointed out inaccuracies and bugs,
offered suggestions on the text, or proposed new topics that should be
covered: Jeff Bauer, Willem Broekema, Thomas Guettler,
@@ -307,7 +316,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node3.html">2 ZODB Programming</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/node3.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/node3.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/node3.html Thu May 1 16:21:15 2003
@@ -46,23 +46,23 @@
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
-<LI><A href="#SECTION000310000000000000000">2.1 Installing ZODB</a>
+<LI><A href="node3.html#SECTION000310000000000000000">2.1 Installing ZODB</a>
<UL>
-<LI><A href="#SECTION000311000000000000000">2.1.1 Requirements</a>
-<LI><A href="#SECTION000312000000000000000">2.1.2 Installing the Packages</a>
+<LI><A href="node3.html#SECTION000311000000000000000">2.1.1 Requirements</a>
+<LI><A href="node3.html#SECTION000312000000000000000">2.1.2 Installing the Packages</a>
</ul>
-<LI><A href="#SECTION000320000000000000000">2.2 How ZODB Works</a>
-<LI><A href="#SECTION000330000000000000000">2.3 Opening a ZODB</a>
-<LI><A href="#SECTION000340000000000000000">2.4 Writing a Persistent Class</a>
-<LI><A href="#SECTION000350000000000000000">2.5 Rules for Writing Persistent Classes</a>
+<LI><A href="node3.html#SECTION000320000000000000000">2.2 How ZODB Works</a>
+<LI><A href="node3.html#SECTION000330000000000000000">2.3 Opening a ZODB</a>
+<LI><A href="node3.html#SECTION000340000000000000000">2.4 Writing a Persistent Class</a>
+<LI><A href="node3.html#SECTION000350000000000000000">2.5 Rules for Writing Persistent Classes</a>
<UL>
-<LI><A href="#SECTION000351000000000000000">2.5.1 Modifying Mutable Objects</a>
-<LI><A href="#SECTION000352000000000000000">2.5.2 Some Special Methods Don't Work</a>
-<LI><A href="#SECTION000353000000000000000">2.5.3 <tt class="method">__getattr__</tt>, <tt class="method">__delattr__</tt>, and <tt class="method">__setattr__</tt></a>
+<LI><A href="node3.html#SECTION000351000000000000000">2.5.1 Modifying Mutable Objects</a>
+<LI><A href="node3.html#SECTION000352000000000000000">2.5.2 Some Special Methods Don't Work</a>
+<LI><A href="node3.html#SECTION000353000000000000000">2.5.3 <tt class="method">__getattr__</tt>, <tt class="method">__delattr__</tt>, and <tt class="method">__setattr__</tt></a>
</ul>
-<LI><A href="#SECTION000360000000000000000">2.6 Writing Persistent Classes</a>
+<LI><A href="node3.html#SECTION000360000000000000000">2.6 Writing Persistent Classes</a>
<UL>
-<LI><A href="#SECTION000361000000000000000">2.6.1 Changing Instance Attributes</a>
+<LI><A href="node3.html#SECTION000361000000000000000">2.6.1 Changing Instance Attributes</a>
</ul></ul>
<!--End of Table of Child-Links-->
<HR>
@@ -608,7 +608,7 @@
that would walk over every single object in a ZODB, checking each one
to see if it's an instance of <tt class="class">User</tt>.
<A NAME="tex2html1"
- HREF="#foot262"><SUP>1</SUP></A>Some OODBs support a feature called extents, which allow quickly
+ HREF="#foot270"><SUP>1</SUP></A>Some OODBs support a feature called extents, which allow quickly
finding all the instances of a given class, no matter where they are
in the object graph; unfortunately the ZODB doesn't offer extents as a
feature.
@@ -619,13 +619,14 @@
<P>
<BR><HR><H4>Footnotes</H4>
<DL>
-<DT><A NAME="foot262">...User.
-</A><A NAME="foot262"
- HREF="node3.html#tex2html1"><SUP>1</SUP></A>
+<DT><A NAME="foot270">...User.
+</A><A
+ HREF="node3.html#tex2html1"><SUP>1</SUP></A></DT>
<DD>XXX is there a convenience method for walking the object graph hiding
somewhere inside DC's code? Should there be a utility method for
doing this? Should I write one and include it in this section?
+</DD>
</DL>
<DIV CLASS="navigation">
<p><hr>
@@ -649,7 +650,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" href="zeo.html">3 ZEO</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/node5.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/node5.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/node5.html Thu May 1 16:21:15 2003
@@ -46,10 +46,10 @@
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
-<LI><A href="#SECTION000510000000000000000">4.1 Subtransactions</a>
-<LI><A href="#SECTION000520000000000000000">4.2 Undoing Changes</a>
-<LI><A href="#SECTION000530000000000000000">4.3 Versions</a>
-<LI><A href="#SECTION000540000000000000000">4.4 Multithreaded ZODB Programs</a>
+<LI><A href="node5.html#SECTION000510000000000000000">4.1 Subtransactions</a>
+<LI><A href="node5.html#SECTION000520000000000000000">4.2 Undoing Changes</a>
+<LI><A href="node5.html#SECTION000530000000000000000">4.3 Versions</a>
+<LI><A href="node5.html#SECTION000540000000000000000">4.4 Multithreaded ZODB Programs</a>
</ul>
<!--End of Table of Child-Links-->
<HR>
@@ -172,7 +172,7 @@
After you call <tt class="method">undo()</tt> you must commit the transaction for the
undo to actually be applied.
<A NAME="tex2html3"
- HREF="#foot583"><SUP>3</SUP></A> There is one glitch in the undo process. The thread
+ HREF="#foot591"><SUP>3</SUP></A> There is one glitch in the undo process. The thread
that calls undo may not see the changes to the object until it calls
<tt class="method">Connection.sync()</tt> or commits another transaction.
@@ -254,14 +254,15 @@
<P>
<BR><HR><H4>Footnotes</H4>
<DL>
-<DT><A NAME="foot583">... applied.</A><A NAME="foot583"
- HREF="node5.html#tex2html3"><SUP>3</SUP></A>
+<DT><A NAME="foot591">... applied.</A><A
+ HREF="node5.html#tex2html3"><SUP>3</SUP></A></DT>
<DD>There are actually two different ways a storage can
implement the undo feature. Most of the storages that ship with ZODB
use the transactional form of undo described in the main text. Some
storages may use a non-transactional undo makes changes visible
immediately.
+</DD>
</DL>
<DIV CLASS="navigation">
<p><hr>
@@ -285,7 +286,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node6.html">5 Related Modules</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/node6.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/node6.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/node6.html Thu May 1 16:21:15 2003
@@ -46,10 +46,12 @@
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
-<LI><A href="#SECTION000610000000000000000">5.1 <tt class="module">ZODB.PersistentMapping</tt></a>
-<LI><A href="#SECTION000620000000000000000">5.2 <tt class="module">ZODB.PersistentList</tt></a>
-<LI><A href="#SECTION000630000000000000000">5.3 BTrees Package</a>
-</ul>
+<LI><A href="node6.html#SECTION000610000000000000000">5.1 <tt class="module">ZODB.PersistentMapping</tt></a>
+<LI><A href="node6.html#SECTION000620000000000000000">5.2 <tt class="module">ZODB.PersistentList</tt></a>
+<LI><A href="node6.html#SECTION000630000000000000000">5.3 BTrees Package</a>
+<UL>
+<LI><A href="node6.html#SECTION000631000000000000000">5.3.1 Total Ordering and Persistence</a>
+</ul></ul>
<!--End of Table of Child-Links-->
<HR>
@@ -70,20 +72,20 @@
<P>
The <tt class="class">PersistentMapping</tt> class is a wrapper for mapping objects
that will set the dirty bit when the mapping is modified by setting or
-deleting a key.
+deleting a key.
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><a name="l2h-1"><tt class="function">PersistentMapping</tt></a></b>(</nobr></td>
<td><var>container = {}</var>)</td></tr></table>
<dd>
-Create a <tt class="class">PersistentMapping</tt> object that wraps the
+Create a <tt class="class">PersistentMapping</tt> object that wraps the
mapping object <var>container</var>. If you don't specify a
value for <var>container</var>, a regular Python dictionary is used.
</dl>
<P>
-<tt class="class">PersistentMapping</tt> objects support all the same methods as
+<tt class="class">PersistentMapping</tt> objects support all the same methods as
Python dictionaries do.
<P>
@@ -93,21 +95,21 @@
</H2>
<P>
-The <tt class="class">PersistentList</tt> class is a wrapper for mutable sequence objects,
-much as <tt class="class">PersistentMapping</tt> is a wrapper for mappings.
+The <tt class="class">PersistentList</tt> class is a wrapper for mutable sequence objects,
+much as <tt class="class">PersistentMapping</tt> is a wrapper for mappings.
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><a name="l2h-2"><tt class="function">PersistentList</tt></a></b>(</nobr></td>
<td><var>initlist = []</var>)</td></tr></table>
<dd>
-Create a <tt class="class">PersistentList</tt> object that wraps the
+Create a <tt class="class">PersistentList</tt> object that wraps the
mutable sequence object <var>initlist</var>. If you don't specify a
value for <var>initlist</var>, a regular Python list is used.
</dl>
<P>
-<tt class="class">PersistentList</tt> objects support all the same methods as
+<tt class="class">PersistentList</tt> objects support all the same methods as
Python lists do.
<P>
@@ -125,9 +127,10 @@
database, unpickling such a large object will be slow. BTrees are a
balanced tree data structure that behave like a mapping but distribute
keys throughout a number of tree nodes. The nodes are stored in
-sorted order. Nodes are then only unpickled and brought into memory
-as they're accessed, so the entire tree doesn't have to occupy memory
-(unless you really are touching every single key).
+sorted order (this has important consequences - see below). Nodes are
+then only unpickled and brought into memory as they're accessed, so the
+entire tree doesn't have to occupy memory (unless you really are
+touching every single key).
<P>
The BTrees package provides a large collection of related data
@@ -135,8 +138,8 @@
handle integer values, which are faster and use less memory. There
are four modules that handle the different variants. The first two
letters of the module name specify the types of the keys and values in
-mappings - O for any object and I for integer. The
-<tt class="module">BTrees.IOBTree</tt> module provides a mapping that accepts integer
+mappings - O for any object and I for integer. For example, the
+<tt class="module">BTrees.IOBTree</tt> module provides a mapping with integer
keys and arbitrary objects as values.
<P>
@@ -150,30 +153,45 @@
building blocks for btrees and tree sets, respectively. A bucket or
set can be used when you are sure that it will have few elements. If
the data structure will grow large, you should use a btree or tree
-set.
+set. Like Python lists, buckets and sets are allocated in one
+contiguous piece, and insertions and deletions can take time
+proportional to the number of existing elements. Btrees and tree sets
+are multi-level tree structures with much better (logarithmic) worst-case
+time bounds.
<P>
The four modules are named <tt class="module">OOBTree</tt>, <tt class="module">IOBTree</tt>,
<tt class="module">OIBTree</tt>, and <tt class="module">IIBTree</tt>. The two letter prefixes are
repeated in the data types names. The <tt class="module">BTrees.OOBTree</tt> module
defines the following types: <tt class="class">OOBTree</tt>, <tt class="class">OOBucket</tt>,
-<tt class="class">OOSet</tt>, and <tt class="class">OOTreeSet</tt>.
+<tt class="class">OOSet</tt>, and <tt class="class">OOTreeSet</tt>. Similarly, the other three modules
+each define their own variants of those four types.
<P>
The <tt class="function">keys()</tt>, <tt class="function">values()</tt>, and <tt class="function">items()</tt>
-methods do not materialize a list with all of the data. Instead, they
-return lazy sequences that fetch data from the BTree as needed. They
-also support optional arguments to specify the minium and maximum
-values to return.
+methods on btree and tree set types do not materialize a list with all
+of the data. Instead, they return lazy sequences that fetch data
+from the BTree as needed. They also support optional arguments to
+specify the minimum and maximum values to return, often called "range
+searching". Because all these types are stored in sorted order, range
+searching is very efficient.
+
+<P>
+The <tt class="function">keys()</tt>, <tt class="function">values()</tt>, and <tt class="function">items()</tt>
+methods on bucket and set types do return lists with all the data.
+Starting in ZODB4, there are also <tt class="function">iterkeys()</tt>,
+<tt class="function">itervalues()</tt>, and <tt class="function">iteritems()</tt> methods that
+return iterators (in the Python 2.2 sense).
<P>
A BTree object supports all the methods you would expect of a mapping
with a few extensions that exploit the fact that the keys are sorted.
The example below demonstrates how some of the methods work. The
-extra methods re <tt class="function">minKey()</tt> and <tt class="function">maxKey()</tt>, which
+extra methods are <tt class="function">minKey()</tt> and <tt class="function">maxKey()</tt>, which
find the minimum and maximum key value subject to an optional bound
-argument, and <tt class="function">byValue()</tt>, which returns value, key pairs
-in reversed sorted order subject to an optional minimum bound argument.
+argument, and <tt class="function">byValue()</tt>, which should probably be ignored
+(it's hard to explain exactly what it does, and as a result it's
+almost never used - best to consider it deprecated).
<P>
<div class="verbatim"><pre>
@@ -184,19 +202,24 @@
4
>>> t[2]
'green'
->>> t.keys()
-<OOBTreeItems object at 0x40269098>
->>> [k for k in t.keys()] # use a listcomp to get a printable sequence
+>>> s = t.keys() # this is a "lazy" sequence object
+>>> s
+<OOBTreeItems object at 0x0088AD20>
+>>> len(s) # it acts like a Python list
+4
+>>> s[-2]
+3
+>>> list(s) # materialize the full list
[1, 2, 3, 4]
->>> [k for k in t.values()]
+>>> list(t.values())
['red', 'green', 'blue', 'spades']
->>> [k for k in t.values(1, 2)]
+>>> list(t.values(1, 2))
['red', 'green']
->>> [k for k in t.values(2)]
+>>> list(t.values(2))
['green', 'blue', 'spades']
->>> t.byValue("glue") # all values > "glue"
-[('spades', 4), ('red', 1), ('green', 2)]
->>> t.minKey(1.5)
+>>> t.minKey() # smallest key
+1
+>>> t.minKey(1.5) # smallest key >= 1.5
2
</pre></div>
@@ -213,6 +236,207 @@
<P>
+<H3><A NAME="SECTION000631000000000000000">
+5.3.1 Total Ordering and Persistence</A>
+</H3>
+
+<P>
+The BTree-based data structures differ from Python dicts in several
+fundamental ways. One of the most important is that while dicts
+require that keys support hash codes and equality comparison,
+the btree-based structures don't use hash codes and require a total
+ordering on keys.
+
+<P>
+Total ordering means three things:
+
+<P>
+
+<OL>
+<LI>Reflexive. For each <var>x</var>, <code><var>x</var> == <var>x</var></code> is true.
+
+<P>
+</LI>
+<LI>Trichotomy. For each <var>x</var> and <var>y</var>, exactly one of
+ <code><var>x</var> < <var>y</var></code>, <code><var>x</var> == <var>y</var></code>, and
+ <code><var>x</var> > <var>y</var></code> is true.
+
+<P>
+</LI>
+<LI>Transitivity. Whenever <code><var>x</var> <= <var>y</var></code> and
+ <code><var>y</var> <= <var>z</var></code>, it's also true that
+ <code><var>x</var> <= <var>z</var></code>.
+</LI>
+</OL>
+
+<P>
+The default comparison functions for most objects that come with Python
+satisfy these rules, with some crucial cautions explained later. Complex
+numbers are an example of an object whose default comparison function
+does not satisfy these rules: complex numbers only support <code>==</code>
+and <code>!=</code> comparisons, and raise an exception if you try to compare
+them in any other way. They don't satisfy the trichotomy rule, and must
+not be used as keys in btree-based data structures (although note that
+complex numbers can be used as keys in Python dicts, which do not require
+a total ordering).
+
+<P>
+Examples of objects that are wholly safe to use as keys in btree-based
+structures include ints, longs, floats, 8-bit strings, Unicode strings,
+and tuples composed (possibly recursively) of objects of wholly safe
+types.
+
+<P>
+It's important to realize that even if two types satisfy the
+rules on their own, mixing objects of those types may not. For example,
+8-bit strings and Unicode strings both supply total orderings, but mixing
+the two loses trichotomy; e.g., <code>'x' < chr(255)</code> and
+<code>u'x' == 'x'</code>, but trying to compare <code>chr(255)</code> to
+<code>u'x'</code> raises an exception. Partly for this reason (another is
+given later), it can be dangerous to use keys with multiple types in
+a single btree-based structure. Don't try to do that, and you don't
+have to worry about it.
+
+<P>
+Another potential problem is mutability: when a key is inserted in a
+btree-based structure, it must retain the same order relative to the
+other keys over time. This is easy to run afoul of if you use mutable
+objects as keys. For example, lists supply a total ordering, and then
+
+<P>
+<div class="verbatim"><pre>
+>>> L1, L2, L3 = [1], [2], [3]
+>>> from BTrees.OOBTree import OOSet
+>>> s = OOSet((L2, L3, L1)) # this is fine, so far
+>>> list(s.keys()) # note that the lists are in sorted order
+[[1], [2], [3]]
+>>> s.has_key([3]) # and [3] is in the set
+1
+>>> L2[0] = 5 # horrible -- the set is insane now
+>>> s.has_key([3]) # for example, it's insane this way
+0
+>>> s
+OOSet([[1], [5], [3]])
+>>>
+</pre></div>
+
+<P>
+Key lookup relies on that the keys remain in sorted order (an efficient
+form of binary search is used). By mutating key L2 after inserting it,
+we destroyed the invariant that the OOSet is sorted. As a result, all
+future operations on this set are unpredictable.
+
+<P>
+A subtler variant of this problem arises due to persistence: by default,
+Python does several kinds of comparison by comparing the memory
+addresses of two objects. Because Python never moves an object in memory,
+this does supply a usable (albeit arbitrary) total ordering across the
+life of a program run (an object's memory address doesn't change). But
+if objects compared in this way are used as keys of a btree-based
+structure that's stored in a database, when the objects are loaded from
+the database again they will almost certainly wind up at different
+memory addresses. There's no guarantee then that if key K1 had a memory
+address smaller than the memory address of key K2 at the time K1 and
+K2 were inserted in a BTree, K1's address will also be smaller than
+K2's when that BTree is loaded from a database later. The result will
+be an insane BTree, where various operations do and don't work as
+expected, seemingly at random.
+
+<P>
+Now each of the types identified above as "wholly safe to use" never
+compares two instances of that type by memory address, so there's
+nothing to worry about here if you use keys of those types. The most
+common mistake is to use keys that are instances of a user-defined class
+that doesn't supply its own <tt class="method">__cmp__()</tt> method. Python compares
+such instances by memory address. This is fine if such instances are
+used as keys in temporary btree-based structures used only in a single
+program run. It can be disastrous if that btree-based structure is
+stored to a database, though.
+
+<P>
+<div class="verbatim"><pre>
+>>> class C:
+... pass
+...
+>>> a, b = C(), C()
+>>> print a < b # this may print 0 if you try it
+1
+>>> del a, b
+>>> a, b = C(), C()
+>>> print a < b # and this may print 0 or 1
+0
+>>>
+</pre></div>
+
+<P>
+That example illustrates that comparison of instances of classes that
+don't define <tt class="method">__cmp__()</tt> yields arbitrary results (but consistent
+results within a single program run).
+
+<P>
+Another problem occurs with instances of classes that do define
+<tt class="method">__cmp__()</tt>, but define it incorrectly. It's possible but
+rare for a custom <tt class="method">__cmp__()</tt> implementation to violate one
+of the three required formal properties directly. It's more common for
+it to fall back" to address-based comparison by mistake.
+For example,
+
+<P>
+<div class="verbatim"><pre>
+class Mine:
+ def __cmp__(self, other):
+ if other.__class__ is Mine:
+ return cmp(self.data, other.data)
+ else:
+ return cmp(self.data, other)
+</pre></div>
+
+<P>
+It's quite possible there that the <tt class="keyword">else</tt> clause allows
+a result to be computed based on memory address. The bug won't show
+up until a btree-based structure uses objects of class <tt class="class">Mine</tt> as
+keys, and also objects of other types as keys, and the structure is
+loaded from a database, and a sequence of comparisons happens to execute
+the <tt class="keyword">else</tt> clause in a case where the relative order of object
+memory addresses happened to change.
+
+<P>
+This is as difficult to track down as it sounds, so best to stay far
+away from the possibility.
+
+<P>
+You'll stay out of trouble by follwing these rules, violating them
+only with great care:
+
+<P>
+
+<OL>
+<LI>Use objects of simple immutable types as keys in
+ btree-based data structures.
+
+<P>
+</LI>
+<LI>Within a single btree-based data structure, use objects of
+ a single type as keys. Don't use multiple key types in a
+ single structure.
+
+<P>
+</LI>
+<LI>If you want to use class instances as keys, and there's
+ any possibility that the structure may be stored in a
+ database, it's crucial that the class define a
+ <tt class="method">__cmp__()</tt> method, and that the method is
+ carefully implemented.
+
+<P>
+Any part of a comparison implementation that relies (explicitly
+ or implicitly) on an address-based comparison result will
+ eventually cause serious failure.
+</LI>
+</OL>
+
+<P>
+
<P>
@@ -238,7 +462,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node7.html">A. Resources</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/node7.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/node7.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/node7.html Thu May 1 16:21:15 2003
@@ -100,7 +100,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node8.html">B. GNU Free Documentation</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/node8.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/node8.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/node8.html Thu May 1 16:21:15 2003
@@ -46,18 +46,18 @@
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
-<LI><A href="#SECTION000810000000000000000">Preamble</a>
-<LI><A href="#SECTION000820000000000000000">B..1 Applicability and Definitions</a>
-<LI><A href="#SECTION000830000000000000000">B..2 Verbatim Copying</a>
-<LI><A href="#SECTION000840000000000000000">B..3 Copying in Quantity</a>
-<LI><A href="#SECTION000850000000000000000">B..4 Modifications</a>
-<LI><A href="#SECTION000860000000000000000">B..5 Combining Documents</a>
-<LI><A href="#SECTION000870000000000000000">B..6 Collections of Documents</a>
-<LI><A href="#SECTION000880000000000000000">B..7 Aggregation With Independent Works</a>
-<LI><A href="#SECTION000890000000000000000">B..8 Translation</a>
-<LI><A href="#SECTION0008100000000000000000">B..9 Termination</a>
-<LI><A href="#SECTION0008110000000000000000">B..10 Future Revisions of This Licence</a>
-<LI><A href="#SECTION0008120000000000000000">ADDENDUM: How to use this License for your documents</a>
+<LI><A href="node8.html#SECTION000810000000000000000">Preamble</a>
+<LI><A href="node8.html#SECTION000820000000000000000">B..1 Applicability and Definitions</a>
+<LI><A href="node8.html#SECTION000830000000000000000">B..2 Verbatim Copying</a>
+<LI><A href="node8.html#SECTION000840000000000000000">B..3 Copying in Quantity</a>
+<LI><A href="node8.html#SECTION000850000000000000000">B..4 Modifications</a>
+<LI><A href="node8.html#SECTION000860000000000000000">B..5 Combining Documents</a>
+<LI><A href="node8.html#SECTION000870000000000000000">B..6 Collections of Documents</a>
+<LI><A href="node8.html#SECTION000880000000000000000">B..7 Aggregation With Independent Works</a>
+<LI><A href="node8.html#SECTION000890000000000000000">B..8 Translation</a>
+<LI><A href="node8.html#SECTION0008100000000000000000">B..9 Termination</a>
+<LI><A href="node8.html#SECTION0008110000000000000000">B..10 Future Revisions of This Licence</a>
+<LI><A href="node8.html#SECTION0008120000000000000000">ADDENDUM: How to use this License for your documents</a>
</ul>
<!--End of Table of Child-Links-->
<HR>
@@ -70,7 +70,10 @@
Version 1.1, March 2000
<BR>
<P>
-Copyright <SPAN CLASS="MATH"></SPAN> 2000 Free Software Foundation, Inc.
+Copyright <SPAN CLASS="MATH"><IMG
+ WIDTH="20" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
+ SRC="img1.gif"
+ ALT="$\copyright$"></SPAN> 2000 Free Software Foundation, Inc.
<BR>
59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
<BR>
@@ -498,7 +501,10 @@
<P>
<P>
-<BLOCKQUOTE>Copyright <SPAN CLASS="MATH"></SPAN> YEAR YOUR NAME.
+<BLOCKQUOTE>Copyright <SPAN CLASS="MATH"><IMG
+ WIDTH="20" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
+ SRC="img1.gif"
+ ALT="$\copyright$"></SPAN> YEAR YOUR NAME.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.1
or any later version published by the Free Software Foundation;
@@ -545,7 +551,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" href="about.html">About this document ...</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/zeo.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/zeo.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/zeo.html Thu May 1 16:21:15 2003
@@ -46,15 +46,15 @@
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
-<LI><A href="#SECTION000410000000000000000">3.1 How ZEO Works</a>
-<LI><A href="#SECTION000420000000000000000">3.2 Installing ZEO</a>
+<LI><A href="zeo.html#SECTION000410000000000000000">3.1 How ZEO Works</a>
+<LI><A href="zeo.html#SECTION000420000000000000000">3.2 Installing ZEO</a>
<UL>
-<LI><A href="#SECTION000421000000000000000">3.2.1 Requirements</a>
-<LI><A href="#SECTION000422000000000000000">3.2.2 Running a server</a>
+<LI><A href="zeo.html#SECTION000421000000000000000">3.2.1 Requirements</a>
+<LI><A href="zeo.html#SECTION000422000000000000000">3.2.2 Running a server</a>
</ul>
-<LI><A href="#SECTION000430000000000000000">3.3 Testing the ZEO Installation</a>
-<LI><A href="#SECTION000440000000000000000">3.4 ZEO Programming Notes</a>
-<LI><A href="#SECTION000450000000000000000">3.5 Sample Application: chatter.py</a>
+<LI><A href="zeo.html#SECTION000430000000000000000">3.3 Testing the ZEO Installation</a>
+<LI><A href="zeo.html#SECTION000440000000000000000">3.4 ZEO Programming Notes</a>
+<LI><A href="zeo.html#SECTION000450000000000000000">3.5 Sample Application: chatter.py</a>
</ul>
<!--End of Table of Child-Links-->
<HR>
@@ -112,7 +112,7 @@
database all the time, this will result in a storm of invalidate
messages being sent, and this might take up more processing time than
the actual database operations themselves.<A NAME="tex2html2"
- HREF="#foot429"><SUP>2</SUP></A>
+ HREF="#foot437"><SUP>2</SUP></A>
<P>
On the other hand, for applications that have few writes in comparison
to the number of read accesses, this aggressive caching can be a major
@@ -369,12 +369,13 @@
<P>
<BR><HR><H4>Footnotes</H4>
<DL>
-<DT><A NAME="foot429">... themselves.</A><A NAME="foot429"
- href="zeo.html#tex2html2"><SUP>2</SUP></A>
+<DT><A NAME="foot437">... themselves.</A><A
+ href="zeo.html#tex2html2"><SUP>2</SUP></A></DT>
<DD>These messages are
small and sent in batches, so there would need to be a lot of writes
before it became a problem.
+</DD>
</DL>
<DIV CLASS="navigation">
<p><hr>
@@ -398,7 +399,7 @@
<b class="navlabel">Up:</b> <a class="sectref" HREF="zodb.html">ZODB/ZEO Programming Guide</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node5.html">4 Transactions and Versioning</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
=== ZODB3/Doc/zodb/zodb.css 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/zodb.css:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/zodb.css Thu May 1 16:21:15 2003
@@ -67,9 +67,19 @@
margin-left: 2em;
margin-right: 2em; }
-div.warning .label { font-size: 110%;
+div.warning .label { font-family: sans-serif;
+ font-size: 110%;
margin-right: 0.5em; }
+div.note { background-color: #fffaf0;
+ border: thin solid black;
+ padding: 0.5em;
+ margin-left: 2em;
+ margin-right: 2em; }
+
+div.note .label { margin-right: 0.5em;
+ font-family: sans-serif; }
+
.release-info { font-style: italic; }
.titlegraphic { vertical-align: top; }
@@ -79,6 +89,10 @@
monospace;
font-size: 90%; }
.verbatim { margin-left: 2em; }
+.verbatim .footer { padding: 0.05in;
+ font-size: 85%;
+ background-color: #99ccff;
+ margin-right: 0.5in; }
.grammar { background-color: #99ccff;
margin-right: 0.5in;
=== ZODB3/Doc/zodb/zodb.html 1.1 => 1.2 ===
--- ZODB3/Doc/zodb/zodb.html:1.1 Fri Jan 17 16:31:06 2003
+++ ZODB3/Doc/zodb/zodb.html Thu May 1 16:21:15 2003
@@ -42,9 +42,9 @@
<center>
<h1>ZODB/ZEO Programming Guide</h1>
<p><b><font size="+2">A.M. Kuchling</font></b></p>
-<p>akuchlin at mems-exchange.org</p>
-<p><strong>Release 0.04</strong><br>
-<strong>January 17, 2003</strong></p>
+<p><span class="email">amk at amk.ca</span></p>
+<p><strong>Release 0.1</strong><br>
+<strong>1 May 2003</strong></p>
<p>
</center>
</div>
@@ -108,6 +108,9 @@
<LI><A href="node6.html#SECTION000610000000000000000">5.1 <tt class="module">ZODB.PersistentMapping</tt></a>
<LI><A href="node6.html#SECTION000620000000000000000">5.2 <tt class="module">ZODB.PersistentList</tt></a>
<LI><A href="node6.html#SECTION000630000000000000000">5.3 BTrees Package</a>
+<UL>
+<LI><A href="node6.html#SECTION000631000000000000000">5.3.1 Total Ordering and Persistence</a>
+</ul>
</ul>
<LI><A href="node7.html">A. Resources</a>
<LI><A href="node8.html">B. GNU Free Documentation License</a>
@@ -149,7 +152,7 @@
</tr></table>
<b class="navlabel">Next:</b> <a class="sectref" href="contents.html">Contents</A>
<hr>
-<span class="release-info">Release 0.04, documentation updated on January 17, 2003.</span>
+<span class="release-info">Release 0.1, documentation updated on 1 May 2003.</span>
</DIV>
<!--End of Navigation Panel-->
More information about the Zodb-checkins
mailing list