title: Red Black Tree versus B Tree
body: <p>I have a project in which I have to achieve fast search, insert and delete operations on data ranging from megabytes to terabytes. I had been studying data structures of late and analyzing them. Being specific, I want to introduce 3 cases and ask questions on that:</p>
  
  <ol>
  <li><p>The data is much more than what the memory can handle (sample ranges in 10-15 terabytes) at one go. In this case, I would store the data structure on a disk.</p></li>
  <li><p>The data is relatively less compared to the memory of the system and thus it can be stored and operated in the memory itself for speed.</p></li>
  <li><p>The data is more than free memory and assume it is less than the size of a possible contiguous chunk of data in the paging file. thus I store the data structure in a file on disk and do a memory mapping of the file.</p></li>
  </ol>
  
  <p>The conclusions I have drawn are:</p>
  
  <p>For case 1, I should use a B-Tree for faster access as it saves on lag produced by disk rotation</p>
  
  <p>For case 2, I should use a Red Black Tree for faster access as data is on memory and no. of elements needed to be scanned in worse case would be lesser than one i have to do if I use B Trees</p>
  
  <p>For case 3, I am doubtful on this one, the page file is on disk uses native OS I/O to operate on files, so should B Tree be a better option or a Red Black tree?</p>
  
  <p>I want to know where the above three conclusions go right and where it goes wrong and how I can improve on performance in the three separate cases.</p>
  
  <p>I am using the C++ Language, with a red black tree and a B tree, both which I have designed from scratch. I am using Boost library for File mapping.</p>
  
  <p>Update 1:: Was reading through <a href="https://stackoverflow.com/questions/647537/b-tree-faster-than-avl-or-redblack-tree">this</a> post in stackoverflow. Got some real good insights, which make me feel that the type of comparisons I have done in the cases may be faulty. A link was posted in the most-voted-for-answer <a href="http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html" rel="noreferrer">http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html</a></p>