title: Why B-Tree for file systems?
body: <p>I know this is a common question and I saw a few threads in Stack Overflow but still couldn't get it. </p>
  
  <p>Here is an accepted answer from Stack overflow:</p>
  
  <blockquote>
    <p>" Disk seeks are expensive. B-Tree structure is designed specifically to
    avoid disk seeks as much as possible. Therefore B-Tree packs much more
    keys/pointers into a single node than a binary tree. This property
    makes the tree very flat. Usually most B-Trees are only 3 or 4 levels
    deep and the root node can be easily cached. This requires only 2-3
    seeks to find anything in the tree. Leaves are also "packed" this way,
    so iterating a tree (e.g. full scan or range scan) is very efficient,
    because you read hundreds/thousands data-rows per single block (seek).</p>
    
    <p>In binary tree of the same capacity, you'd have several tens of levels
    and sequential visiting every single value would require at least one
    seek. "</p>
  </blockquote>
  
  <p>I understand that B-Tree has more nodes (Order) than a BST. So it's definitely flat and shallow than a BST.</p>
  
  <p>But these nodes are again stored as linked lists right? </p>
  
  <p>I don't understand when they say that the keys are read as a block thereby minimising the no of I/Os.</p>
  
  <p>Isn't the same argument hold good for BSTs too? Except that the links will be downwards? </p>
  
  <p>Please someone explain it to me?</p>