| ▲ | hinkley 2 hours ago | ||||||||||||||||
It all ends up back at B trees. Why does it always end up back at B trees? At this point have we optimized hardware to assume B trees in a sort of self-fulfilling prophesy? | |||||||||||||||||
| ▲ | alfiedotwtf 38 minutes ago | parent | next [-] | ||||||||||||||||
B trees are more friendly to being cache oblivious | |||||||||||||||||
| ▲ | crest an hour ago | parent | prev | next [-] | ||||||||||||||||
Binary trees have worse cache locality. The cost of accessing memory has grown so much compared to computation that supposedly slower "heavy weight" data structures are worth it now (as in the last 10-20 years). | |||||||||||||||||
| |||||||||||||||||
| ▲ | wrs 2 hours ago | parent | prev [-] | ||||||||||||||||
Yes, that hardware is called "the memory cache". B-trees were invented because disk reads were very expensive. Now, memory cache fills are very expensive. | |||||||||||||||||