Difference between binary search tree and m-way tree

Question

Please explain the difference between a binary search tree and m-way tree?

Answer 1

A binary search tree has only two fixed branches and is therefore a lot easier to implement. m-way trees such as B-trees are generally used when the tree has to be stored on disk rather than in memory. Examples include file systems and database indexes.

Answer 2

A binary tree is a special case of an m-way tree with only one "value" per node (m = 1) and you either move down to the left or the right link.

              +----+
              | 20 |
              +----+
              |    |
         +----+    +----+
         |              |
      +----+         +----+
      |  1 |         | 23 |
      +----+         +----+

An m-way tree can have more than one "value" per node but the theory is still the same: you choose which link to move down to and there's m+1 possible choices. An m-way tree (where m is 2) can look like this:

              +----+----+
              | 10 | 20 |
              +----+----+
              |    |    |
     +--------+    |    +--------+
     |             |             |
+----+----+   +----+----+   +----+----+
|  1 |  5 |   | 12 | 18 |   | 23 | 24 |
+----+----+   +----+----+   +----+----+

These m-way trees are often used in situations where you can fit more than one value in an efficient block (by efficient, I mean one that can be read and written efficiently, like a disk block, sector, cluster or cylinder depending on how your storage subsystem operates). For example, if a disk block is 512 bytes, the values take up 122 bytes and the links take up 4 bytes, you can fit 4 values in a disk block, calculated as follows:

numvals = int ((blocksize - linksize) / (valuesize + linksize))
        = int ((   512    -     4   ) / (   122    +     4   ))
        = int (          508          /            126        )
        = int (                    4.0317                     )
        =                             4

That gives you four values (4 x 122 = 488) and five links (5 x 4 = 20) for a total of 508 bytes. Although there's some wastage, this has the advantage of storing an integral number of values in each efficient block.