<div dir="ltr"><div>The conversation at the last meeting sparked my interest to implement the file-based binary search tree. </div><div><br></div><div><a href="https://github.com/despertargz/tree-binary-search-file/blob/master/lib/Tree/Binary/Search/File.pm">https://github.com/despertargz/tree-binary-search-file/blob/master/lib/Tree/Binary/Search/File.pm</a><br></div><div><br></div><div>Build the file:</div><div>my $file = Tree::Binary::Search::File->new("/tmp/test-bst");<br></div><div>$file->write_file({ test => "blah" });</div><div><br></div><div>Reading values:</div><div><div>my $file = Tree::Binary::Search::File->new("/tmp/test-bst");<br></div></div><div>my $value = $file->get("test");</div><div><br></div><div>It performed well against a file-based, linear search. You can see how the linear search doubles as the records doubles. Haven't measured to see how close to O(log n) it is, but it appears to do well. It barely flinches when going from 1 to 2 million records.</div><div><br></div><div>Time is seconds to locate single record (worst-case-scenario)</div><div><br></div><div># of records, binary-search-tree, linear<br></div><div><div>1024, 4.48226928710938e-05, 0.000963926315307617</div><div>2048, 4.31537628173828e-05, 0.00278782844543457</div><div>4096, 3.38554382324219e-05, 0.00162196159362793</div><div>8192, 5.07831573486328e-05, 0.0121698379516602</div><div>16384, 4.60147857666016e-05, 0.0115268230438232</div><div>32768, 6.58035278320312e-05, 0.0142660140991211</div><div>65536, 0.000729084014892578, 0.0285739898681641</div><div>131072, 0.00218009948730469, 0.0539009571075439</div><div>262144, 0.00141692161560059, 0.1079261302948</div><div>524288, 0.0019831657409668, 0.214764833450317</div><div>1048576, 0.00240302085876465, 0.434930086135864</div><div>2097152, 0.00240802764892578, 0.875269889831543</div></div><div><br></div><div>The header format is</div><div>[left-node position][right-node position][value length][key][value]</div><div><br></div><div>It currently uses a static key size, so it can read in the key along with the rest of the header. This takes up more disk space but should be faster than an extra read. If there's any natural buffering of the file though then this may not incur a performance penalty so I'll have to benchmark.</div><div><br></div><div>This is the main search logic</div><div><br></div><div><div>    my $header;</div><div>    read $fh, $header, $HEADER_SIZE;</div><div><br></div><div>    my $file_key = substr($header, 12, $KEY_SIZE);</div><div>    my $val_len  = unpack("V", substr($header, 8, 4));</div><div>    my $right    = unpack("V", substr($header, 4, 4));</div><div>    my $left     = unpack("V", substr($header, 0, 4));</div><div><br></div><div>    my $comp = $key cmp $file_key;</div><div><br></div><div>    if ($comp == 0) {</div><div>        my $val;</div><div>        read $fh, $val, $val_len;</div><div>        return $val;</div><div>    }</div><div>    elsif ($comp == -1) {</div><div>        if ($left == 0) {</div><div>            return undef;</div><div>        }</div><div><br></div><div>        $self->find_key($key, $left);</div><div>    }</div></div><div><div>    else {</div><div>        if ($right == 0) {</div><div>            return undef;</div><div>        }</div><div><br></div><div>        $self->find_key($key, $right);</div><div>    }</div></div><div><br></div><div>The writing of the file sorts the key/value pairs, builds a BST, while building the BST a 'flat' list of the nodes is built along with the positions of their left and right node. Recording the position of the node itself made writing the file easier, then this is fed to a method which writes each node to the file. </div><div><br></div><div>The writing of the file is not memory-efficient as it builds the BST in memory for simplicity, though this cost is only incurred once when the file is written. If it could both insert and balance the file-based tree then this would be ideal so I'll have to look into some ways to do that. <br></div><div><br></div><div>Another consideration would be storing all the values at the end of the file so the headers run sequentially. Especially if the values are longer, this could improve cache hits / buffering.<br></div><div><br></div><div>It's a work-in-progress as I need to make some methods private, make key-size configurable, add documentation and tests, then I might see if I can upload to cpan. </div><div><br></div><div>Anyways, just wanted to share. Let me know what you think. Always enjoy the talks and the technical discussions that ensue :)</div><div><br></div><div><br></div><div>Best Regards,</div><div>Christopher Mevissen</div><div><br></div></div>