By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,213 Members | 2,172 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,213 IT Pros & Developers. It's quick & easy.

Hashtable or Btree?

P: n/a
I've got 100MB of urls organized by domain and then by document. I
thought that a hastable of hastables or a btree of btrees would be a
good way to lookup a specific url quickly by first finding the domain
and then finding the matching document. What do you think would be
better? And do you have any implementation you recommend?

Thanks, and merry Christmas folks.

-Dan
Jul 22 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
"Eloff" <da*******@gmail.com> wrote in message
news:48**************************@posting.google.c om...
I've got 100MB of urls organized by domain and then by document. I
thought that a hastable of hastables or a btree of btrees would be a
good way to lookup a specific url quickly by first finding the domain
and then finding the matching document. What do you think would be
better? Probably hash table.
Note that in this case it is potentially unnecessary to make a
hash table of hash tables - hasing the full URL once might do as well.
And do you have any implementation you recommend?

The pre-standard hash_map or unordered_map that your standard library
implementation is very likely to include should work well.

If anything was to be optimized, it is probably more on the side
of the string storage... eventually.
hth -Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Jul 22 '05 #2

P: n/a
Eloff wrote:
I've got 100MB of urls organized by domain and then by document.
I thought that a hastable of hastables or a btree of btrees
would be a good way to lookup a specific url quickly by first
finding the domain and then finding the matching document. What
do you think would be better? And do you have any implementation
you recommend?


I don't see why you would need containers of containers. Your key could
be the (domain, document) tuple or just the URL, for either hashtables
or btrees.

None of the C++ standard containers sound suitable for this. hash_map
is not standard, and while std::map is, and probably does use a tree,
it is not going to be a btree. Also, those sorts of containers would
build data structures in memory, rather than operating on the file
directly. I don't of know of any popular libraries that would do what
you need either. Most people would just use a database; you could try
Google for "embedded database". I found some in C, but not C++.
--
Dave O'Hearn

Jul 22 '05 #3

P: n/a
"Eloff" <da*******@gmail.com> wrote in message
news:48**************************@posting.google.c om...
I've got 100MB of urls organized by domain and then by document. I
thought that a hastable of hastables or a btree of btrees would be a
good way to lookup a specific url quickly by first finding the domain
and then finding the matching document. What do you think would be
better? And do you have any implementation you recommend?

Thanks, and merry Christmas folks.

-Dan


I recommend you put your data in a database first. Then you can use any
programming language to search as you please using SQL queries. A good free
database is mysql:

http://www.mysql.com/

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 22 '05 #4

P: n/a
Dave O'Hearn wrote:
...
I don't see why you would need containers of containers. Your key could
be the (domain, document) tuple or just the URL, for either hashtables
or btrees. If you have many documents per domain, it could make sense to organize
the data this way in order to reduce memory consuption.

...
you need either. Most people would just use a database; you could try
Google for "embedded database". I found some in C, but not C++.

sqlite (www.sqlite.org) may be a good choice ...

greetings
Martin
Jul 22 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.