node37.html 7.79 KB
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<link rel="STYLESHEET" href="zodb.css" type='text/css'>
<link rel="first" href="zodb.html" title='ZODB/ZEO Programming Guide'>
<link rel="contents" href="contents.html" title="Contents"><link rel='last' href='about.html' title='About this document...'>
<link rel='help' href='about.html' title='About this document...'>

<LINK REL="previous" HREF="node36.html">
<LINK REL="up" HREF="node34.html">
<LINK REL="next" HREF="node38.html">
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name='aesop' content='information'>
<META NAME="description" CONTENT="5.3 BTrees Package">
<META NAME="keywords" CONTENT="zodb">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<title>5.3 BTrees Package</title>
</head>
<body>
<DIV CLASS="navigation">
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td><A HREF="node36.html"><img src='icons/previous.gif'
  border='0' height='32'  alt='Previous Page' width='32'></A></td>
<td><A HREF="node34.html"><img src='icons/up.gif'
  border='0' height='32'  alt='Up One Level' width='32'></A></td>
<td><A HREF="node38.html"><img src='icons/next.gif'
  border='0' height='32'  alt='Next Page' width='32'></A></td>
<td align="center" width="100%">ZODB/ZEO Programming Guide</td>
<td><A href="contents.html"><img src='icons/contents.gif'
  border='0' height='32'  alt='Contents' width='32'></A></td>
<td><img src='icons/blank.gif'
  border='0' height='32'  alt='' width='32'></td>
<td><img src='icons/blank.gif'
  border='0' height='32'  alt='' width='32'></td>
</tr></table>
<b class="navlabel">Previous:</b> <a class="sectref" HREF="node36.html">5.2 ZODB.PersistentList</A>
<b class="navlabel">Up:</b> <a class="sectref" HREF="node34.html">5 Related Modules</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node38.html">A. Resources</A>
<br><hr>
</DIV>
<!--End of Navigation Panel-->

<H2><A NAME="SECTION000630000000000000000">
5.3 BTrees Package</A>
</H2>

<P>
When programming with the ZODB, Python dictionaries aren't always what
you need.  The most important case is where you want to store a very
large mapping.  When a Python dictionary is accessed in a ZODB, the
whole dictionary has to be unpickled and brought into memory.  If
you're storing something very large, such as a 100,000-entry user
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).

<P>
The BTrees package provides a large collection of related data
structures.  There are variants of the data structures specialized to
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
keys and arbitrary objects as values.

<P>
The four data structures provide by each module are a btree, a bucket,
a tree set, and a set.  The btree and bucket types are mappings and
support all the usual mapping methods, e.g. <tt class="function">update()</tt> and
<tt class="function">keys()</tt>.  The tree set and set types are similar to mappings
but they have no values; they support the methods that make sense for
a mapping with no keys, e.g. <tt class="function">keys()</tt> but not
<tt class="function">items()</tt>.  The bucket and set types are the individual
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.

<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>.

<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.

<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
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.

<P>
<div class="verbatim"><pre>
&gt;&gt;&gt; from BTrees.OOBTree import OOBTree
&gt;&gt;&gt; t = OOBTree()
&gt;&gt;&gt; t.update({ 1: "red", 2: "green", 3: "blue", 4: "spades" })
&gt;&gt;&gt; len(t)
4
&gt;&gt;&gt; t[2]
'green'
&gt;&gt;&gt; t.keys()
&lt;OOBTreeItems object at 0x40269098&gt;
&gt;&gt;&gt; [k for k in t.keys()] # use a listcomp to get a printable sequence
[1, 2, 3, 4]
&gt;&gt;&gt; [k for k in t.values()]
['red', 'green', 'blue', 'spades']
&gt;&gt;&gt; [k for k in t.values(1, 2)]
['red', 'green']
&gt;&gt;&gt; [k for k in t.values(2)]
['green', 'blue', 'spades']
&gt;&gt;&gt; t.byValue("glue") # all values &gt; "glue"
[('spades', 4), ('red', 1), ('green', 2)]
&gt;&gt;&gt; t.minKey(1.5)
2
</pre></div>

<P>
Each of the modules also defines some functions that operate on
BTrees - <tt class="function">difference()</tt>, <tt class="function">union()</tt>, and
<tt class="function">difference()</tt>.  The <tt class="function">difference()</tt> function returns
a bucket, while the other two methods return a set.
If the keys are integers, then the module also defines
<tt class="function">multiunion()</tt>.  If the values are integers, then the module
also defines <tt class="function">weightedIntersection()</tt> and
<tt class="function">weighterUnion()</tt>.  The function doc strings describe each
function briefly.

<P>


<P>

<DIV CLASS="navigation">
<p><hr>
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td><A HREF="node36.html"><img src='icons/previous.gif'
  border='0' height='32'  alt='Previous Page' width='32'></A></td>
<td><A HREF="node34.html"><img src='icons/up.gif'
  border='0' height='32'  alt='Up One Level' width='32'></A></td>
<td><A HREF="node38.html"><img src='icons/next.gif'
  border='0' height='32'  alt='Next Page' width='32'></A></td>
<td align="center" width="100%">ZODB/ZEO Programming Guide</td>
<td><A href="contents.html"><img src='icons/contents.gif'
  border='0' height='32'  alt='Contents' width='32'></A></td>
<td><img src='icons/blank.gif'
  border='0' height='32'  alt='' width='32'></td>
<td><img src='icons/blank.gif'
  border='0' height='32'  alt='' width='32'></td>
</tr></table>
<b class="navlabel">Previous:</b> <a class="sectref" HREF="node36.html">5.2 ZODB.PersistentList</A>
<b class="navlabel">Up:</b> <a class="sectref" HREF="node34.html">5 Related Modules</A>
<b class="navlabel">Next:</b> <a class="sectref" HREF="node38.html">A. Resources</A>
<hr>
<span class="release-info">Release 0.04, documentation updated on 17 January 2003.</span>
</DIV>
<!--End of Navigation Panel-->

</BODY>
</HTML>