From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.224.74.72 with SMTP id t8mr1592788qaj.4.1378230227930; Tue, 03 Sep 2013 10:43:47 -0700 (PDT) X-Received: by 10.49.94.39 with SMTP id cz7mr52692qeb.26.1378230227903; Tue, 03 Sep 2013 10:43:47 -0700 (PDT) Path: border1.nntp.dca3.giganews.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!q10no2532162qai.0!news-out.google.com!p7ni567qas.0!nntp.google.com!j7no157985qai.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Tue, 3 Sep 2013 10:43:47 -0700 (PDT) In-Reply-To: <31834951-571f-4361-b18a-e0abde8fa219@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=105.236.92.252; posting-account=p-xPhAkAAADjHQWEO7sFME2XBdF1P_2H NNTP-Posting-Host: 105.236.92.252 References: <9fc26b8a-7a5c-4941-81cb-8f0e9c17a660@googlegroups.com> <31834951-571f-4361-b18a-e0abde8fa219@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: B-tree performance From: Peter Brooks Injection-Date: Tue, 03 Sep 2013 17:43:47 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Original-Bytes: 2286 Xref: number.nntp.dca.giganews.com comp.lang.ada:183268 Date: 2013-09-03T10:43:47-07:00 List-Id: On Tuesday, 3 September 2013 18:14:19 UTC+2, Dan'l Miller wrote: >=20 >=20 > So it would make sense to not use a B-tree. Indeed, it would make sense = to not restart the comparison again at each node, because it wastes time an= d bloats memory-space. Hence, it would make sense to use a radix trie. ht= tp://en.wikipedia.org/wiki/Radix_trie >=20 Yes, that might make sense. I did something similar many years ago when I p= roduced correlation matrices of letter sequences in words. It wouldn't work= as a linked list, but a multi-dimensional associative array might be an op= tion - thank you, I'll look into that. One pleasant side-effect of this method would be that it'd be much easier t= o search for the same entry in different URIs. I'll have to experiment a bit on workable representations of this. The funny thing about this is that it might be very easy to implement in aw= k. Not what I was looking for or thinking of. I'm not sure how awk behaves = with very large arrays - I'll find out quite soon.