What would you build using a multiway search tree.

Question

I am currently teaching myself about various data strutures and am a little frustrated with the various types of trees. I can understand the purpose of organizing something into binary search trees but don't see any practical application of multiway search trees. Can someone please give some examples of problems they've implemented using multiway search trees?

Answer 1

Multiway trees are used to implement data structures on disk, like a relational database table.

A seek operation on disk is very slow compared to a contiguous read. So, for efficiency, a structure that minimizes the number of seeks is best. The depth of a multiway tree is much less than a binary tree for the same elements, meaning that few seeks on disk are required to locate a node.