|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
February 18th, 2003, 12:42 PM
|
|||
|
|||
|
on-disc binary tree?
(in regards to my previous thread on storing millions of IPs to disc:
http://forums.devshed.com/showthrea...&threadid=50109) Can I create a binary tree that is stored on disc? Then only modify the section(s) of the file to modify the binary tree as each node is added? I always thought you had to read in the entire file and re-write the entire file to disk whenver a change is made, but this is not the case, is it?
__________________
Matthew Doucette / Xona.com
|
|
#2
February 19th, 2003, 03:07 PM
|
|||
|
|||
|
IMHO
you would probably want to convert all pointers in your structs to relative pointers (= "-5 records from here" or "+2 records from here") and write it to disk like that. on reading the tree you would back-convert. but for sure, there is no way to insert data in the middle of a file, so it would need a re-organization then-and-when ("defrag"  ) or some care on loading the file.never tried this though.... but for my recent project, 3D worlds, i'll need binary trees too in the near future. This will be my first approach until i get my a** up on reading about "BSP trees" that from my knowledge right now do take care of exactly this problem... ... just 2ect for my thoughts on this ...
__________________
-- Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.
|
|
#3
February 20th, 2003, 08:37 AM
|
|||
|
|||
|
Quote:
|
|
#4
February 20th, 2003, 01:24 PM
|
||||
|
||||
|
You could also allocate a file that is large enough to hold all the possible entries. Then all you need to do is compute the offset for an entry and increment the counter. This may take up a lot more space (32 MB), but if you have plenty of hard disk space, this isn't such a bad plan. Besides, you don't need to implement a binary tree at all with this method. All you need to do is compute the offset for a given IP address and fseek(3) to that area of the file. It's quick, simple and gets the job done!
|
|
#5
February 20th, 2003, 02:07 PM
|
|||
|
|||
|
Good idea, but it does not allow me to store anything but an increment counter. I may be storing additional information with each IP, like the referrer perhaps.
Interesting idea though. Assuming I wanted to store only an increment, and only increment up to 255, it would take 256^4 * 1 byte / 1024 / 1024 / 1024 = 4 GB discspace, that is quite a lot. There are probably IP ranges that do not exist however. Anyone know what they are?
|
|
#6
February 20th, 2003, 02:35 PM
|
|||
|
|||
|
Another idea:
A 256 branch, 4-Level, b-tree. The IPs would be "stored" in the location of their data. Each IP is four nodes of one byte each. The left nodes are the only nodes which store the IP's data. Last edited by Doucette : February 20th, 2003 at 02:40 PM.
|
|
#8
February 26th, 2003, 01:16 PM
|
|||
|
|||
|
Quote:
|
|
#9
February 26th, 2003, 01:36 PM
|
||||
|
||||
|
Nothing to it really. Just open the file in read-write mode, seek to the offset and write your data. Here's some sample code for you to peruse:
Code:
FILE *fp;
if ((fp = fopen("test.txt", "r+w")) == NULL) {
fprintf(stderr, "Could not open test.txt\n");
return(1);
}
/* Compute where we want to put data */
offset = ComputeOffset();
/* Seek to offset bytes from beginning of file */
fseek(fp, offset, SEEK_SET);
/* Write to the file */
fputs(data, fp);
fclose(fp);
The only thing you need to worry about is the size of the file. Like you said, it's going to be huge 
|
|
| Viewing: Dev Shed Forums > Programming Languages > C Programming > on-disc binary tree? |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
