search

EFanZh / Introduction-to-Algorithms

Implementations of algorithms and solutions to exercises and problems from the book Introduction to Algorithms, Third Edition.
https://efanzh.org/2018/10/05/introduction-to-algorithms-exercises.html
18 stars 4 forks source link

Why search for B+ tree is faster than B tree? #7

Open NaNAGISaSA opened 2 years ago

NaNAGISaSA commented 2 years ago

I am wondering why search for B+ tree is faster than B tree, and find that nearly no resources on the network talked about that. I think that because B+ tree internal nodes does not need to save data pointers, so it can save more keys than B tree, and the height of B+ tree can be smaller than B tree, which makes the search process faster. But when the order of B tree is equal to B+ tree, I think the search time complexity of B tree and B+ tree is equal, so it can not be faster. Am I right? Thank you! Besides, there is an answer talking about cache hit rate for B tree and B+ tree which I am not fully understand, is this the key for reducing searching time?

EFanZh commented 2 years ago

Hi @NaNAGISaSA, unfortunately, I haven’t learnt about B+ trees. I’ll have to look it up before having any opinions.