<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2653.12">
<TITLE>RE: Skip Lists?!</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>> Hmm, with "main" memory being so much slower than cache, btrees might</FONT>
<BR><FONT SIZE=2>> even start making sense for in-memory structures. But not necessarily</FONT>
<BR><FONT SIZE=2>> for Squeak, where an "array of foo's" won't necessarily have </FONT>
<BR><FONT SIZE=2>> all of the</FONT>
<BR><FONT SIZE=2>> foo's next to each other, anyway, and thus where accessing </FONT>
<BR><FONT SIZE=2>> items within</FONT>
<BR><FONT SIZE=2>> a node still causes fetches to distant parts of memory.</FONT>
</P>
<P><FONT SIZE=2>You might want to take a look at:</FONT>
</P>
<P><FONT SIZE=2>Cache Conscious Indexing for Decision-Support in Main Memory </FONT>
<BR><FONT SIZE=2>(Jun Rao and Kenneth Ross at Columbia University)</FONT>
</P>
<P><FONT SIZE=2><A HREF="http://citeseer.nj.nec.com/rao99cache.html" TARGET="_blank">http://citeseer.nj.nec.com/rao99cache.html</A></FONT>
</P>
<P><FONT SIZE=2>If the foo's are SmallInteger's, it could be interesting, but probably</FONT>
<BR><FONT SIZE=2>not for the general case. </FONT>
</P>
<P><FONT SIZE=2>-david</FONT>
</P>
</BODY>
</HTML>