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?
(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?
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 ...
Originally posted by M.Hirsch
IMHOthere 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.
I am only storing IPs, so there will only be nodes added and nodes modified (increment counters on each IP), no nodes deleted. This removes the need for defrag. This tree will also be completely reset each day, even though it may grow to be 1 or 2 million nodes in size.
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?
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?
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.
Originally posted by ahuimanu You should be able to use fixed-length records (esp with IP addresses) to make a random access file?
J
This is exactly what I plan on doing. I just have never coded anything in any language where I do not write out an entire file. Is there anything special in coding a program that modifies only the middle of a file, for example?
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?
) or some care on loading the file.
Guest Post at 2010-5-13 05:55
