[ZODB-Dev] OOBTree: Persistent Objects as keys

[Thomas Guettler]

This is a multi-part message in MIME format.
--------------060205020708010105020607
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

Jim Fulton wrote:

>
>Thomas Guettler wrote:
>
>>Toby Dickenson wrote:
>>
>...
>
>>If the tree of BTree would use type(obj) at the first level it should work:
>>
>>BTree
>>|-strings ["foo", "foo2", ...]
>>|-FooObjects
>>|-Integers
>>
>
>I don't know what this means.
>
I attached a gif that should make this more clear.
A tree is a hierarchical datastructure with one root.
What I mean with "first level" are the knots which can be accessed directly
from the root. One solution would be to have at the first level one knot 
for
each type of key. Then you only compare objects of the same type in the
sub-trees.

When a new item is added you check if the type ("integer") of the key 
has already a corresponding
sub-tree. If not create one, then add the item to the other objects of 
type "integer".

If you want to get an item, you check the type of the key. If the key is 
an integer you
search in the integers sub-tree, if it is a string you search in the 
"strings" subtree.

In XML this would look like this:

<knot>
  <knot value="integers">
      <knot value="1"/>
      <knot value="2"/>
  </knot>
  <knot value="strings">
    <knot value="a">
    <knot value="b">
  </knot>
</knot>


Tell me if it is unclear. English is not my native language.

 thomas

--------------060205020708010105020607
Content-Type: image/gif;
 name="btree.gif"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="btree.gif"

R0lGODlhZQGcAPcAAAAAAAQEBAgICAwMDBAQEBgYGBwcHCAgICQkJCgoKCwsLDAwMDQ0NDg4
ODw8PEBAQEREREhISExMTFBQUFVVVVlZWV1dXWFhYWlpaXFxcXV1dXl5eX19fYGBgYWFhYmJ
iY2NjZWVlZmZmZ2dnaGhoaWlpa6urrKysra2tr6+vsLCwsbGxsrKys7OztLS0tbW1tra2t7e
3ubm5u7u7vLy8vb29v///wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACwAAAAAZQGcAAAI/wBtCBxIsKDBgwgTKlzIsKHD
hwtBAJhIsaLFixVBQNzIsaPHjyBDihxJsqTJkw8vjAg54gLKlzBjypxJs6ZNkSpZurzJs6fP
n0CDzswJsqXQo0iTKl16k2hCGQuNMp1KtarVqwKdHqSBIOpOrGDDih1rUmvBEw66KpRKtq3b
t3AHmiXoAYbahGzj6oVZwwOHv4ADCx4MOMVesXML3kWY97DjkSMWEJ48OcOBx1gTE1x8sDHm
zxw9b4xxGTRVzQM5GxRtuvXarx5Ju2aKWqDqgqxn6x6Y26Hs3UgTrFQ4wSvw47hhL6zbouBv
5EAfDP/YGzro6gNbkLgAleBz6zxnMP+Y7hE7eMe5ZXjwEMIGjAsX2nsvfd5miATjddbfnRvB
iRYTyHfQd/vBlMICGMhQW0PmFQhXbjDYIIMGHiREoIMlvRDBA83ZsCBDDWLYVm4XODDBBBUi
dKGIIM2QQQIoEPShcSx+xloLDghEoYX0tUYARkAGKUB3C/V1gEYFSRTkkhYhWeNjHVhQUIAI
yICABxqcyKNuAIh0QAwMmZDABjM8aWZCFVBQUAgpFCdDCxFGqGKPpnUZ0pcKrfDABGCe6edq
ahJEAg0kPLQiZnaChOdBMlTQgGF/RjrQCgcE+tGhjyX60aIEzcDBASVIKmqjDXCgHEeYOqap
R5wKdB8HNYj/GukMG4BqQ4hzcullnzYcmKCskd7nQay3njoanaCt2hGeGnIILE8jUCbttNQC
xitDKCBI5K2SVUuZZaDVgEIGD9SgLEcHuPBijM/yBIC38ML7AAcNaRhBh53GS5kJmKXwAEUZ
2HDuRgMU4GS7Nw1M018LybBuuzMsQFFzCj9EwAHkIVxTxTIxjFBfCRz8rAcCAPCAQBw3lO4F
DbygsU0pw+SxQSWMWabGG2DQAgH8CryrDSsskOLLMqW8rQ0hCPjRzJM2UMG1z9ZQQYopEBvz
QovWsMECKxAdU8rFEZQCpCAxHYOjXb88wwOhGnS1Qq220MAGxHpt0rkksNfrlTaQ/3ACm4aR
kILe7rF3QuCEG+QxrQm0/XIMDaTt9s8FeQCj3XcbtF0LIUxAgwPNIRDfejaIjmMIMjhwAglX
bt75QQwLW7fGQbuM0NsJtTpQDBFccDPmISkbggNkh60W6WrlTfgF7BGfEAcVJPCr1yU88PtB
uCOkO0EjNA588AcNj4AGNhgvEPICteDBBJCSLj75BkEggApJzTD2/fjnr//+/PfvfwrXMwgI
KjA77P3vgCkoANQK0qgIHI0gNUDgAQtYI2WdIEJcKZ9tzlchtagvBPBD0QVtkEHFRS9jP5nA
Ah7Awha68IUwjKEMZyjDBYTtIBgIGEMmQMMetjACATwICv9ChpAX+bCHCdDhmZSVAgdgqTgT
uEAJ0WcD9dnAAfBxgOCcmCXYcWAGF3iA7aJDNqX46yA1iIDSlOKilhlkRq/507nehK/mdIgG
NKjiQPD4JgU1h44I8diBhuaTB5QxKWdkYAPYVZWgDWsgNYAjXowlouwlpInayRFDZqa1yP3E
kFNJZHYagC+raI1rNvBABiTJGEpiyJKXXM8DvViQFcyNgjMBZULWw0sP5LEj6nGIKHv1gAVa
5QUNwIAABDABFAqKBLPkjSsdBMuRMG0gHkDlTXSJkPVM4Eq+9IgGEHBIhIhyBEB0CwImggBn
2oZCDohmsc60gglUUyTXHAgyfWf/E27uUpPu0WMVS9mCUqYmBNMcSCI3cAFcYmUEFBmAO0HI
wUk+yQQPaIAJ7hmSfHLvcjTxZzcB6oCSpk4DXYSBE+FTkO2UriH+iiQhyZKCv0QAYwy5QKFa
yaLusQ9l+goqZebVsAhMIJqeEqpgRiDSg3iApCdA2k4oNIGdgo4gP40PQ5oYAXe2ZUEkAGhn
ErqbGYCgABcYow1MoNS2BiaIBxGTMyPjVg5YpqkGeepAruoBBPgVARNIy1+HZqUTlRREASgn
XGqjAbGOFSJMPaJkJ+tDkTVEBrXKgDyxAsYIqHWeICENXitH0uZgSSAySB2kSnlagThPISkw
wAM2OxbU/7CURg55AAgkyNve8g8EJzPUBQ7gAbi2JVtDGwGuBnSA0dKltBJSHY5OgJYWnKBK
qZET0m5oTkMuQLFfdSfreAle0Oa2vEAZpkJaUAGMOfQtneScAD5A1oWIFr0CSYGAQvBLGGAJ
UiegEJFoQEgCL+SMMiCqXjSjvPWUF1fOTW9wFYKCByzAcaBZQQICAIAFuJK7qYSBQe8byglz
YLZxYeVjHxLhn6gXNwuIAH4PY8+JSAkhi9EOd5zT3Bn3ZJgH8vFpvOoQCKP3m3/l20b6ioCS
RvXAE4YgCA5wAYO2pgQVsZRBEJC3Qr1Hq/NpsU/Um2B6uUXFq6nvQMTcgts4hP90e9tqlCXE
gQJkwJiziaAGKpAQ0zmRR2L+8ZwFcmLaTgXNyYEIm+8Sn3ie4EQ7fXRV6TI0N4ttwjHAwAG+
uJ/+CESlgBbyTV6c3++SBdHcU7NAFr3XKjcxjxM4nANg/eRUomh98IPtydh7gBC89zi5Aail
Rbtb3xrbt8B9ioIV8oJj58/KHLnABpx9P4YqesZt3qtpbx3F9XnzK1gq6DhpmwIFWBjDBfJ0
rxw7nxNT9t3wbqFlC1JohQgg3i8cUkiqh28XonshrHbttnkZAm+vR0BwtsGOFHKCAIjgSY2h
UulQ9Frm6iXICeGoQLYXloBfsTkuTSUJQu6BnaYyRZ//M7k5GxBoYCuHTcWBQR8VkqqwlPl2
lGuLxyfQoRJpyUMm4i6T/ZrrS1ovAv+uT2MGpXL7Iust9S6Ixm3AcbC0fNQnk9oala7qXDkG
471CWc7JcnWbiBIDG8DQcg1Sc7KU+QUC4NfUq46VstdkmB7oumnWzmPQbKBkC/DZnfBcd1Gb
fc7o/LVu+D4f0FyAIhsd+1jsTpMXo6ABxp0BD/vNeR9CG7IF6HwDnh4XSlFEYpIXC+VnQuoW
LMCYQaa27P93ATN/JIKzT8FnH6PfDExdABwwtEL43fmkJyQCK+y88l8YYxWR0iCkRopHvze5
kBDAAAWogPFzOm3ZW/shMsi9//j1J88EMzK/g07K9KlPkLlLoAQlqEABMLD7haBamsDRfNtm
EMH0S9/27Idzd8ICCwAVMnAfCYA6DnF/AsF4bSE1IFADbBN9AHIQtdYxABiA1acoMRB/BPEC
GJB9PaMQDGhewJEBCmAy0RdQBgFiMpOBGth+P6N9NDMBdvZZdYMaT6VFcYQcvjcR1YMQ7+Eh
61McrBNzJwI/AIIiLgEDSVg4E6ABThhFCrF+Gjh3YCIDBcgoIJAACxACN+MXWeFOr/Y58uSA
x1URFeB/OFI6hcI8GlQ6zYFSH1c+OYIAc6gBbXYCMhBrIvc8MBiDYjd4AuGBCdECGEAAFSAm
AKARmv9BA93hANqVZtYxLglAAOyWPneYXxVSHG22HuOUAjuBSeA0Tm2ocA4QApNoEBqQdiGx
ArlHeKqSczS4ECXgABTREkTWJtOEhnFhAplYRZtYRZ1YReC0HiGHI5/IS6fYK+NUdAWBixdg
eAVhAqHHeQ2QAFySewo0EFpoaBhQERBAZDTQRBeYaOdBgcNoRZ6TOvnFHbMGdO7YK1WmSTvW
jIpzAOSyabLIU6FFeo8RRp03AbNjiMTxABvAASbQVQnxSwlHienIhsXhQRVSIjAQViUFciZC
hxgJOhVoA2gRWOdIEHaVADMQA5/SVYqXaiHRdn5SiwsoXjsBZisGHivYEL//RAPyUXB75BF/
wRYocAFoJTk9eCkAKSnfmBJeFVgmUpTWcZMQ4QAoFU/4RC8RcH4zMAKj5wGyWB0w8Ete9zIG
mVNExiB6x3v+1xEFRRIMIwMmyXa1opKQxC69kTqfJxAu+ScwaX9lCSJn+XVpKRQekxtBOX9d
MwIE0By5gRZ4SHNHOSpbSJb6EZFVMTNXqRAzEALZeAAAQAAxACF1uCV2M5YJUYK+CBdQCRQz
45bGRRAoQBEHQF8LcVWiaTd7iRCm+ZeHkQIEsHy+6ULExZILsQEVoQAJRZth6TVJSYJ9iVs2
OX7QeT8FdJnDNzaxUh3IaXHAQ5oGYUScl0SCiBKs//kQ2HmXNpCXonKbBYF7s7eS4RkaqlYd
/OWY1Lec79kW1OmXLfmY7cKd9wkW46mf/xiA6vmfD1VfvoiesmKfBhoW+WlRAxqA/tmgVRGg
EGqUMVigFEoV1YFOs1cC/KkxDLqhVvGgBvECy+eKGkiaKFlXHNCPJAoRFhqjIrGXFzABdUWF
MVgD20cSp0mjqBWZHtKcTsl+Z+WeIGGiQOoRBpmbO1oAjTgTM7qkHkGDM0ABRHqhRjoRBYCk
1KGbVOqNFxZ6Zfk3RQo8NQClEzFvJ6GkYQp+EgMA+fEUSuaP7PcCHGABm7Z14vmWb7oRMqCm
ACAcxAGHWsp+qVkSPxqjMv8QjgBgAF7VS2f6PYlaEg+KosqHAQbaAg9AAO7khCc3qcBTqSRh
oR4qeyBKoQx5EN12Ig8GppFCqj76FQkaot+jGSLWAigFlhCpgbJKEtRZqxS6IA/ZqwH4qyPB
mkEJq+dpq8CzIHgkqpiDrCMRAuv0AK7EmC7YeA3qpDFIrSGBAmpqnH3WHAhVm//prb4amC/R
Fz8CAGiFEDqpieh6n+p6rOwKEwoCAAFAVpOWnPaapXaKr0FBKVp2ELcFsO95r4iarzLRG1Lp
dMOKo26lo+sqFMHGp33XoC3gohxgnl4DrrOKEKzzV9uKl876p+8pspDBrAqqsoLIsiIhrDBL
pTL/O5kYWrNLerNF4bIpq7MEGxQ0C7QxyrNfup9ES6NG6xEbxSRO22FJW7QOG7VU62JTW7VY
e3hZu7VIsbRc+7Ub4bVgO7ZyRrZmW3lXe7ZqG7Zpu7ZuW7ZvG7chIbZyS7Z0W7dgWwNEibd8
27d++7eAG7iCO7iEW7iGqxAqVVKKm4oe0nWrmBXMmhAq9biHWyMtAACLW1Lt8XMNYa0HcVgv
cbkgW7n7Iboi0VefG4wiYbqkeyasuybtQWBOKEVIU1IaABVtciWHBLrQVyIXICckoDQhsFOi
iEVy8rqta7kAAG2H1WaK6yHglBa98k0esLuZSAIAwDwXQE59sxhc1jfZ/5t33Iu8ySsil5u5
O9G8AJBr3yshR5VKt8G7mzE0JWIb8sE6tkG/OUK+5esgl0shBOda+7u8e3Ulk4i6BiG/6QMA
JFBQ2gEAEVK/5eMSl9vABYW9IkbA/csi/HtFA4wvfbhO43M+8ctuHgAASeZXzZECVWIlhnHC
KYyHHbzB59HB6mtlugoA7YHA0chuLBxNV+K5e/NAM0zD1mHDH4xaFYdF8Ju6BmElCBePqWS7
qIUAUUwDRWzEyIHEVaTBHpwC6gMAUYW9GrC7x7geeaQBAOABnDPCVYxdOrLGbUw+WazFwDG5
CNuEkigjfqU6AxFYa1QimSsnT9VkM5Ww55MWfxTmHntsx478yJAcyZI8yZRcyVQREAA7
--------------060205020708010105020607--