directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From <aok...@bellsouth.net>
Subject [database] Skiplist's are probabilistic BTrees
Date Mon, 17 Nov 2003 04:18:34 GMT
Another research item to digest on the database side.  From what I understand they out perform
the conventional binary tree algorithm which our default backend is based on.  Perhaps one
day this might be worth more consideration however again I want to note it on the list for
future reference.

"A skip list is a probabilistic alternative to binary trees. They seem to be a smart and efficient
way of achieving a similar objective, i.e. doing what binary trees are good at."

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

Alex



Mime
View raw message