Re: [tkined] SNMP to SQL

From: George Ross (
Date: Thu Feb 24 2000 - 10:05:22 MET


Content-Type: text/plain; charset=us-ascii

We're drifting rather off-topic here, but...

> Presumably if the data is already in sorted order when you put the record
> in the table, that will speed up the process of indexing it.

Well, not necessarily. I don't know the internal details of any of the
database systems you're using, but to illustrate the point suppose they're
using a simple Btree index.

If you insert the keys in ascending order then either the operation will be
O(n) as the tree becomes in effect a linked list, and performance will keep
getting worse as n grows, or there'll be some kind of rebalancing act every
so often as the database tries to keep reasonably O(log n). OTOH, if the
keys were coming in essentially at random then the tree would naturally
tend to stay reasonably well balanced and insertion would actually run
faster on average than the sequential case.

In other words, it's not quite as obvious as might appear at first sight,
and the results you achieve will certainly depend on the importance that
the database system author put on optimising for sequential keys. There
may be hooks, or you may have to give some hints, or you may just be out
of luck. In the latter case I suppose you could trade off insert-time
efficiency against retrieval-time efficiency by adding a non-sequential
component to your keys.
- --
Dr George D M Ross, Division of Informatics, University of Edinburgh
     Kings Buildings, Mayfield Road, Edinburgh, Scotland, EH9 3JZ
Mail: Voice: +44 131 650 5147 Fax: +44 131 667 7209
 PGP: 1024/B74A4F7D 14 E8 B3 00 20 04 68 F8 95 40 CB 36 A4 D4 FA 90

Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv


!! This message is brought to you via the `tkined & scotty' mailing list.
!! Please do not reply to this message to unsubscribe. To subscribe or
!! unsubscribe, send a mail message to <>.
!! See for more information.

This archive was generated by hypermail 2b29 : Mon Jan 08 2001 - 15:27:37 MET