출처:http://stackoverflow.com/questions/6211118/b-trees-vs-binary-trees 4 down vote Algorithmic complexity is the same, since O(log b n) = O(c log n) = O(log n) but the constant factors are hugely different. B-trees were designed for platter hard disks, which have a huge access time (moving the head into position) after which an entire physical sector is read. Making the B-tree nodes as large as the sector minimizes the number of access times and maximizes the useful data out of each read operation. But if you are working out of memory (or SSD) you have a negligible access time, therefore a better comparison is to count the number of single words accessed. For example, let's plan a data structure to store 2 20 keys of 1 word each, for a total of 4MiB of raw data on a 32bit machine. A "beefy" B-tree, made for contemporary hard disks, will have 4kiB nodes, which can hold up to 512 keys and pointers (...