[asterisk-users] AstDB/Berkely DB - Hash function? Balanced-Tree? b-Tree? Linked List?

Karl Fife asterisk-users at kfife.mailworks.org
Fri Aug 15 00:56:49 CDT 2008


Does anyone know enough about the implementation of AstDB to know
whether the data structure is a Hash function, a Balanced-Tree, a
b-Tree, or a Linked List? 

I'm trying to estimate the lookup 'cost' of a AstDB with around 160,000
keys?  Obviously I already know that it WILL WORK, but the question is
whether the data structure is optimal in the Berkeley DB AS IMPLEMENTED
in Asterisk.  AstDB just like CURL is missing some of its features as
implemented, so the generic Berkeley Doc doesn't help much. 

The key-space is ideal.  It's just npa/nxx lookups so it's UNIQUE and
EVENLY DISTRIBUTED--a perfect for a hash function (or even a balanced
tree).  What I do NOT want is a 150k member linked list, or even a
standard b-tree that ends up being 160k entries tall because the values
were inserted in order etc.  

In terms of Databases, I know that 160K keys is very small potatoes, but
I want to make sure I understand what's going on under the hood so that
my lookup costs are as low as possible.  

Lookups on my Oracle database with tens of millions of records are
instantaneous and inexpensive when implemented properly, and about ten
thousand times slower (actually) when done improperly.  If a database
has only 160K keys, it can be tough to tell whether the data structures
are being used efficiently, because even WILDLY INEFFICIENT lookups seem
fast.

Can anyone speak to this?  
What is the default data structure?
How many records have you stuck into the AstDB?  

Thank you!
-Karl Fife




 



More information about the asterisk-users mailing list