directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From <aok...@bellsouth.net>
Subject Re: [database] Skiplist's are probabilistic BTrees
Date Mon, 17 Nov 2003 04:23:06 GMT
Oh I forgot another really good link or two on skiplists:

http://citeseer.nj.nec.com/cache/papers/cs/1389/ftp:zSzzSzftp.cs.umd.eduzSzpubzSzpaperszSzpaperszSzncstrl.umcpzSzCS-TR-2286.1zSzCS-TR-2286.1.pdf/pugh90skip.pdf

This is an applet demo of the algorithm - darn microsoft products don't have the vm so I can't
see it till later.

http://iamwww.unibe.ch/~wenger/DA/SkipList/


> 
> From: <aok123@bellsouth.net>
> Date: 2003/11/16 Sun PM 11:18:34 EST
> To: <directory-dev@incubator.apache.org>
> Subject: [database] Skiplist's are probabilistic BTrees
> 
> 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