Re: Hash Tables

OOOOPS: You ever have one of those days. Everything I did was just sort of right. The following sentence is still wrong. > The depth of the tree divided by 2 is on average the number of nodes > that you visit to find any key value ( that is where my formula is off > ) here is the real average number of leaves visited. refer to tree graph below: The equation below is the number of total leaves visited to look at each node in the tree 1*1 + 2*2 + 3*4 + 4*8 + 5*16 = 129 so the average for this case is 4.16... for 6 nodes it is 4.16 -> 31 5.01 -> 63 and so on So it is log shaped but I can't so easily give you the exact equation for the average. Knuth does of course and I would look a lot smarter now if I could just find one of my two copies. Sorry, I had the best of intentions. :-) Here I felt so bad I used a spread sheet and .. Depth Num on Leaf Total in Tree Access Total Access Average 1 1 1 1 1 1 2 2 3 4 5 1.6666666667 3 4 7 12 17 2.4285714286 4 8 15 32 49 3.2666666667 5 16 31 80 129 4.1612903226 6 32 63 192 321 5.0952380952 7 64 127 448 769 6.0551181102 8 128 255 1024 1793 7.031372549 9 256 511 2304 4097 8.0176125245 10 512 1023 5120 9217 9.0097751711 11 1024 2047 11264 20481 10.005373718 12 2048 4095 24576 45057 11.002930403 13 4096 8191 53248 98305 12.001587108 14 8192 16383 114688 212993 13.000854544 15 16384 32767 245760 458753 14.000457778 16 32768 65535 524288 983041 15.000244144 17 65536 131071 1114112 2097153 16.000129701 18 131072 262143 2359296 4456449 17.000068665 19 262144 524287 4980736 9437185 18.00003624 20 524288 1048575 10485760 19922945 19.000019074 21 1048576 2097151 22020096 41943041 20.000010014 22 2097152 4194303 46137344 88080385 21.000005245 23 4194304 8388607 96468992 184549377 22.000002742 24 8388608 16777215 201326592 385875969 23.000001431 25 16777216 33554431 419430400 805306369 24.000000745 26 33554432 67108863 872415232 1677721601 25.000000387 27 67108864 134217727 1811939328 3489660929 26.000000201 28 134217728 268435455 3758096384 7247757313 27.000000104 29 268435456 536870911 7784628224 15032385537 28.000000054 30 536870912 1073741823 16106127360 31138512897 29.000000028 31 1073741824 2147483647 33285996544 64424509441 30.000000014 32 2147483648 4294967295 68719476736 1.3314398618e+11 31.000000007 33 4294967296 8589934591 1.4173392077e+11 2.7487790694e+11 32.000000004 34 8589934592 17179869183 2.9205777613e+11 5.6693568307e+11 33.000000002 So it appears to be depth - 1 or log_based_2( N+1 ) - 1 curtis@crowson1.com (Curtis Crowson) wrote in message news:<eb5a5e2b.0401301110.6c3002bf@posting.google.com>... > > hash size is purportedly 32 + keysize + rowsize (of the selected data). > > > > Interesting formula you've got there, I'll have to take a closer look. > > > > cheers > > j. > > > > My index time formula is slightly off but the shape is correct. > Basically the depth of the btree* ( or plus it only matters slightly > which informix standard indexes are ) is some function of the number > of nodes in the tree. For a binary-tree each node one key and has two > children branches. > > x represents the nodes at each level > > Level > 0 1 2 3 4 > x x x x x > x x x x > x x x > x x x > x x > x x > x x > x x > x > x > x > x > x > x > x > x > > So the number of nodes in this tree are: > 1 + 2 + 4 + 8 + 16 = 31 > or mo' betta > 2^0 + 2^1 + 2^2 + 2^3 + 2^4 which is equal to > (2^5) - 1 > > So if your index is 5 deep like our tree it will contain 31 nodes > > if n1 = n2 then > > lg_base_2( n1 ) = lg_base_2( n2 ) > > lg_base_2( 31 + 1 ) = 5 > The depth of the tree divided by 2 is on average the number of nodes > that you visit to find any key value ( that is where my formula is off > ) > > lg_base_2( N )/ 2 = average number of nodes to visit. I am also > assuming that the nodes are completely filled which isn't true. Knuth > would be really mad at me. ;-) So you multiple by the time it takes to > visit a node and add any fixed time and you have the formula for index > accesses. > > The scan formula is left as an exercise. ;-)