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.
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
doing 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.
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.
Otherwise, you will have to implement a data structure that maintains this
information on top of the Elephant infrastructure.
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.
http://en.wikipedia.org/wiki/Red-black_tree
There is a lisp example of this data structure here:
http://www.aviduratas.de/lisp/progs/rb-trees.lisp
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?
Just remember that premature optimization is one of the four horseman of the
apocalypse for the effective programmer.
Ian
----- Original Message -----
From: Mariano Montone
To: Elephant bugs and development
Sent: Wednesday, October 03, 2007 6:57 PM
Subject: [elephant-devel] Collection paging
Hello, it's me again :S.
I would like to know how I can access persistent collection pages efficiently.
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.
The collection size problem was treated here:
http://common-lisp.net/pipermail/elephant-devel/2007-October/001162.html.
But now I have a problem with building the pages.
My first try was:
(let*
((start (* (current-page self) (page-size self)))
(end (+ start (page-size self)))
)
(<:ul
(elephant:map-btree #'(lambda (key elem) (declare (ignore key))
(let ((elem-text (make-elem-text self elem)))
(<:li
(if (slot-value self 'selectable)
(<ucw:a :action (answer elem) (<:as-html
elem-text))
(<:a (<:as-html elem-text))))))
(model self) :start start :end end)
)
with start and end previously fixed based in the current page number and size.
But I realized indexes were not sequential when I created new objects, as
this shows:
ASKIT> (with-btree-cursor (cursor (find-class-index 'user))
(iter
(for (values exists? k v) = (cursor-next cursor))
(while exists?)
(format *standard-output* "~A -> ~A ~%" k v)))
2 -> #<USER name: dssdf {B043379}>
3 -> #<USER name: ttttt {B045C69}>
5 -> #<USER name: ff {B048179}>
6 -> #<USER name: other {B04A451}>
7 -> #<USER name: guest {AD61271}>
100 -> #<USER name: qqq {B053001}>
101 -> #<USER name: {B055721}>
102 -> #<USER name: {B057E01}>
103 -> #<USER name: {B05A529}>
104 -> #<USER name: {B05CCF1}>
105 -> #<USER name: {B05F579}>
106 -> #<USER name: {B063E91}>
107 -> #<USER name: qqq {B066851}>
200 -> #<USER name: {B069519}>
201 -> #<USER name: {B06C009}>
300 -> #<USER name: {B06EBA1}>
301 -> #<USER name: aaa {B0717D1}>
NIL
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?
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).
Thank you again :)
Mariano
------------------------------------------------------------------------------
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
