B-tree

Это вдогонку к metakit...

Б-деревья позволяют организовать очень быстрый поиск при очень малом количестве обращений...

Вот примерно так и выглядит Б-дерево (картинка взята с algolist.manual.ru, там же можно почерпнуть больше информации...). В этом дереве за 3 обращения можно добраться до любого ключа, т.е. если сгруппировать по 100 ключей на узел, то можно за 3 обращения найти любой из 1000000 ключей. А уж как это применить придумать можно с легкостью... Б-деревья, например, используются в некоторых файловых системах NTFS,ReiserFS и массе других.

Ну не совсем Б-деревья... точнее в вышеперечисленных ФС используются Б+деревья, разница в том, что все ключи храняться в листьях. Во внутренних узлах храняться лишь копии ключей, которые помогают искать нужные листья.