News for hackers. Stuff that matters.
Re:How does SQLite work? Part 1: Pages by michaelmcmillan on Sunday September 28, 2014 @05:48AM (#8379321)
btree is probably "binary tree".
Re:How does SQLite work? Part 1: Pages by josephlord on Sunday September 28, 2014 @06:29AM (#8379373)
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.
Re:How does SQLite work? Part 1: Pages by basiliothecat on Sunday September 28, 2014 @07:17AM (#8379446)
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.

Re:How does SQLite work? Part 1: Pages by josephlord on Sunday September 28, 2014 @01:15PM (#8380278)
Thanks I said I was rusty although I guess there is an added insertion and maybe deletion cost in keeping it sorted.
Re:How does SQLite work? Part 1: Pages by basiliothecat on Sunday September 28, 2014 @06:31AM (#8379376)
It's [B-Tree](http://en.wikipedia.org/wiki/B-tree) - a generalization of binary search tree.