[DB] B트리와 Binary트리의 성능 차이

출처:http://stackoverflow.com/questions/6211118/b-trees-vs-binary-trees

4 down vote

Algorithmic complexity is the same, since O(logb 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 220 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 (more or less). A depth of 2 with 100% fill holds 218 keys, so we need a depth of 3. What is the average search going to look like? On average it will have to read 3/8 (half of the average fill 3/4) of every node in its path, from the root all the way down = 4608 words. A binary search tree will have 220 nodes, each holding one key and two pointers (3 words). Depth will be 20. The average search will have to read the key and one of the pointers from each node in its path, from the root all the way down = 40 words. Memory caching can possibly alleviate the difference, but cannot reverse these numbers. Update On the other hand, memory-only B-trees with a much more limited branching factor appear to perform better than binary trees in practice. 32 keys per node in particular seems to be a sweet spot for current architectures, both 32- and 64-bit. A few newer languages are even using 32-key B-trees as a builtin data structure, alongside hash tables or as a replacement for them (eg. Clojure.) This result may be due to the fact that, although the words accessed by a B-tree algorithm are more than those of a binary tree, the number of cache misses (read operations that cause the CPU to stall and wait for the main RAM) may be lower than in a binary tree, if the caching architecture can fetch chunks of RAM that contain an entire B-tree node at a time. Here we are again, the optimization is the same as for disk-based mass storage, where we use B-trees with nodes as large as the physical sector, to minimize access times. In this case, we use a B-tree with nodes as large as the read operation that is performed by the Level 3 cache against the RAM, to minimize cache misses.