<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2900.3157" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2>When you say indexes are not sequential, do you
mean UIDs are not sequentially allocated? I think there is a BDB sequence
issue that I've never worried about that jumps to the nearest 100 when you
reconnect. However, if you create anything other than a user object, you
will also have gaps in the UID sequence so that's a fundamental issue.
Don't assume anything about UIDs other than the fact that they are
unique.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>You could create and index your own field which is
a sequential ID for creation ordering, but it sounds like you probably want to
return a sublist based on some sort order like alphabetical by name or by
date. In this case, at least d</FONT><FONT face=Arial size=2>oing the last
page is easy, map from end and count the # of users you want before you
terminate, but to find an element that is N elements away from the first or last
element in less than O(n) time isn't possible with the underlying B-Trees we're
using.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>
<DIV><FONT face=Arial size=2>The first question is whether you database is
guaranteed to be so big that you can't just do this linear time. When you
start to face performance issues, then you can look at building that additional
data structure.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>Otherwise, you will have to
implement a data structure that maintains this information on top of the
Elephant infrastructure. </FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>The first idea that occurs to me is to drop the
idea of using an indexed class or standalone btrees and just build a red-black
tree using object slots (you can inherit from a base class that implements the
RB tree functionality). This simultaneously solves the count problem and
the access element # N problem. The O(log (base 2) N) lookup time will
have a higher fixed cost per level traversal, but if you start getting really
large dbs (1000's to 10k's?) then it will certainly beat a linear map-index
approach. i.e.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2><A
href="http://en.wikipedia.org/wiki/Red-black_tree">http://en.wikipedia.org/wiki/Red-black_tree</A></FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>There is a lisp example of this data structure
here:</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2><A
href="http://www.aviduratas.de/lisp/progs/rb-trees.lisp">http://www.aviduratas.de/lisp/progs/rb-trees.lisp</A></FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Now there is a problem that you'll need one of
these for each sorted order which for a list sorted many different ways is a
problem. Anyone know how SQL query systems implement this?</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Just remember that premature optimization is one of
the four horseman of the apocalypse for the effective programmer.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Ian<A
href="http://en.wikipedia.org/wiki/Red-black_tree"></A></FONT></DIV>
<BLOCKQUOTE
style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<DIV style="FONT: 10pt arial">----- Original Message ----- </DIV>
<DIV
style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B>
<A title=marianomontone@gmail.com
href="mailto:marianomontone@gmail.com">Mariano Montone</A> </DIV>
<DIV style="FONT: 10pt arial"><B>To:</B> <A
title=elephant-devel@common-lisp.net
href="mailto:elephant-devel@common-lisp.net">Elephant bugs and development</A>
</DIV>
<DIV style="FONT: 10pt arial"><B>Sent:</B> Wednesday, October 03, 2007 6:57
PM</DIV>
<DIV style="FONT: 10pt arial"><B>Subject:</B> [elephant-devel] Collection
paging</DIV>
<DIV><BR></DIV>Hello, it's me again :S.<BR><BR>I would like to know how I can
access persistent collection pages efficiently.<BR><BR>What I'm trying to do
is making work a web list component with elephant. The list component is
supposed to support well known navigation commands, like look at the
collection in pages, support for first, last, next, previous buttons, and
display of collection size. <BR><BR>The collection size problem was treated
here: <A
href="http://common-lisp.net/pipermail/elephant-devel/2007-October/001162.html">http://common-lisp.net/pipermail/elephant-devel/2007-October/001162.html</A>.<BR><BR>But
now I have a problem with building the pages. <BR><BR>My first try
was:<BR> (let*<BR> ((start (*
(current-page self) (page-size self)))<BR>
(end (+ start (page-size self)))<BR>
)<BR>
(<:ul<BR>
(elephant:map-btree #'(lambda (key elem) (declare (ignore
key))<BR>
(let ((elem-text
(make-elem-text self elem)))<BR>
(<:li<BR>
(if (slot-value self 'selectable)
<BR>
(<ucw:a
:action (answer elem) (<:as-html elem-text))<BR>
(<:a (<:as-html
elem-text))))))<BR>
(model self) :start start :end
end)<BR> ) <BR><BR>with start
and end previously fixed based in the current page number and size.<BR><BR>But
I realized indexes were not sequential when I created new objects, as this
shows:<BR><BR>ASKIT> (with-btree-cursor (cursor (find-class-index 'user))
<BR> (iter <BR> (for (values exists? k v) =
(cursor-next cursor))<BR> (while
exists?)<BR> (format *standard-output* "~A -> ~A ~%" k
v)))<BR>2 -> #<USER name: dssdf {B043379}> <BR>3 -> #<USER
name: ttttt {B045C69}> <BR>5 -> #<USER name: ff {B048179}> <BR>6
-> #<USER name: other {B04A451}> <BR>7 -> #<USER name: guest
{AD61271}> <BR>100 -> #<USER name: qqq {B053001}> <BR>101 ->
#<USER name: {B055721}> <BR>102 -> #<USER name:
{B057E01}> <BR>103 -> #<USER name: {B05A529}> <BR>104 ->
#<USER name: {B05CCF1}> <BR>105 -> #<USER name:
{B05F579}> <BR>106 -> #<USER name: {B063E91}> <BR>107 ->
#<USER name: qqq {B066851}> <BR>200 -> #<USER name:
{B069519}> <BR>201 -> #<USER name: {B06C009}> <BR>300 ->
#<USER name: {B06EBA1}> <BR>301 -> #<USER name: aaa
{B0717D1}> <BR>NIL<BR><BR>I don't think this is a bug, it must have to do
with how Elephant manages btrees; but then how am I supposed to access through
pages?<BR>I would like to have to access all the objects from the beggining
just to discard them instantly (imagine a large collection and the user
wanting to see the last page). <BR><BR>Thank you again :)<BR><BR>Mariano<BR>
<P>
<HR>
<P></P>_______________________________________________<BR>elephant-devel site
list<BR>elephant-devel@common-lisp.net<BR>http://common-lisp.net/mailman/listinfo/elephant-devel</BLOCKQUOTE></BODY></HTML>