B-Tree RDBS のインデックスで使われている ブロックデバイス(ex. HDD)と相性がいいので 検索, worst caseでも O(logN) 派生: B+Tree 参考文献 なぜBTreeがIndexに使われているのか - maru source