Hacker News new | past | comments | ask | show | jobs | submit login

No it isn't. A btree is a structure specially optimised to minimise the number of pages that need to be loaded to traverse the tree. I'm sure Google will find you some good details but basically every node has as many children as can be fitted in a disk block. The linear time search within the node is faster than additional page missed that a log(n) descent of a binary tree would be. Details may be wrong it has been 15 years since my algorithms course and I've never implemented a Btree although everyone has probably used thousands of them in databases and file systems.



The linear time search within the node

It's even better - logarithmic as the internal nodes have thier keys sorted and you can binary search within one.


Thanks I said I was rusty although I guess there is an added insertion and maybe deletion cost in keeping it sorted.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: