9 ms·

How does SQLite work? Part 1: Pages

149 points by jvns 12y ago

bane 12y ago
Great analysis. The beauty of it is that SQLite uses the free-est possible license ever conceived, in every possible sense of the word. In a million years, the SQLite source will be entirely unencumbered from any restrictions, philosophies, moral leanings or uses. You can literally do anything you want with the SQLite source, quaint ideas like the GPL are merely a minor subset of the possibilities, most of which haven't even been conceived of yet. It's so free that if you don't like the license it's published under, you can fork it, place it under the license you feel comfortable with and nobody cares. It's likely that the license the SQLite source has been published under will withstand entire shifts of civilizations, economic theories, governments and more yet to be imagined. Future evolved species, with entirely different modes of cognition will still be able to work with it without worrying about tangling with any legal issues. When the invasion of alien lawyers happens, the only software they'll bring back to their home planet will be software similarly unencumbered. For the GPLv3, they'll annihilate our world.
- teddyh 12y ago
  Copyrights do expire, you know.
  - bane 12y ago
    Not according to Disney.
- rdc12 12y ago
  Why would an invading alien enemy give a damn about the licences used on earth. Thou I do love the idea of the MPAA and co trying to fight copyright on a galactic scale
  - bane 12y ago
    They're aliens, who knows how they think? After all the Vogons are basically intergalactic bureaucrats.
- masklinn 12y ago
  > You can literally do anything you want with the SQLite source Unless you live in a country where you can't put things in the public domain, which is most of them (even in the US reading such a possibility is debatable and debated), then you literally can't do anything with the SQLite source, at least not with any legal recourse.
acqq 12y ago
I really appreciate how Julia Evans enjoys experimenting in programming and how she can carry that to her readers. That's so refreshing, compared to so many practitioners who just read the books and often uncritically "believe" the written texts.
wirrbel 12y ago
Great read on so many levels! Its accessible writing while getting to the core of such a well-known database.
everettForth 12y ago
I have heard SQLite described as "alien technology". Super fun blog way of looking at it!
michaelmcmillan 12y ago
btree is probably "binary tree".
- deleted 12y ago
  [deleted]
- josephlord 12y ago
  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.
  - basiliothecat 12y ago
    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.
    - josephlord 12y ago
      Thanks I said I was rusty although I guess there is an added insertion and maybe deletion cost in keeping it sorted.
- basiliothecat 12y ago
  It's [B-Tree](http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree) - a generalization of binary search tree.
Jgrubb 12y ago
Hey there, I found these two books lsat summer when I wanted to know more about all this computer-science-y, data-structure-y stuff that I didn't know much about because of being self taught. Data Structures Succinctly 1 & 2. https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=data%20structures%20succinctly https://www.google.com/webhp?sourceid=chrome-instant&ion=1&e... Linking to Google search because they are behind a registration wall, but I haven't gotten an email from them yet. All the code examples are in C#, but they were both really good reads. I also found this a really good read for diving deep into how indexes work -- http://sql-performance-explained.com/ http://sql-performance-explained.com/
- ufmace 12y ago
  This site was linked somewhere here a while back - http://use-the-index-luke.com/ http://use-the-index-luke.com/ I learned a lot about how indexes work from it.
  - Jgrubb 12y ago
    Yeah, that book I linked is the same guy as that site you linked. Good stuff.
grayclhn 12y ago
If you like this post, you should follow her twitter, where she's live-tweeting sqlite: https://twitter.com/b0rk https://twitter.com/b0rk

149 points by jvns 12y ago

bane 12y ago

Great analysis. The beauty of it is that SQLite uses the free-est possible license ever conceived, in every possible sense of the word. In a million years, the SQLite source will be entirely unencumbered from any restrictions, philosophies, moral leanings or uses. You can literally do anything you want with the SQLite source, quaint ideas like the GPL are merely a minor subset of the possibilities, most of which haven't even been conceived of yet. It's so free that if you don't like the license it's published under, you can fork it, place it under the license you feel comfortable with and nobody cares. It's likely that the license the SQLite source has been published under will withstand entire shifts of civilizations, economic theories, governments and more yet to be imagined. Future evolved species, with entirely different modes of cognition will still be able to work with it without worrying about tangling with any legal issues. When the invasion of alien lawyers happens, the only software they'll bring back to their home planet will be software similarly unencumbered. For the GPLv3, they'll annihilate our world.

teddyh 12y ago
Copyrights do expire, you know.
- bane 12y ago
  Not according to Disney.
rdc12 12y ago
Why would an invading alien enemy give a damn about the licences used on earth. Thou I do love the idea of the MPAA and co trying to fight copyright on a galactic scale
- bane 12y ago
  They're aliens, who knows how they think? After all the Vogons are basically intergalactic bureaucrats.
masklinn 12y ago
> You can literally do anything you want with the SQLite source Unless you live in a country where you can't put things in the public domain, which is most of them (even in the US reading such a possibility is debatable and debated), then you literally can't do anything with the SQLite source, at least not with any legal recourse.

acqq 12y ago

I really appreciate how Julia Evans enjoys experimenting in programming and how she can carry that to her readers. That's so refreshing, compared to so many practitioners who just read the books and often uncritically "believe" the written texts.

wirrbel 12y ago

Great read on so many levels! Its accessible writing while getting to the core of such a well-known database.

everettForth 12y ago

I have heard SQLite described as "alien technology". Super fun blog way of looking at it!

michaelmcmillan 12y ago

btree is probably "binary tree".

deleted 12y ago
[deleted]
josephlord 12y ago
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.
- basiliothecat 12y ago
  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.
  - josephlord 12y ago
    Thanks I said I was rusty although I guess there is an added insertion and maybe deletion cost in keeping it sorted.
basiliothecat 12y ago
It's [B-Tree](http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree) - a generalization of binary search tree.

Jgrubb 12y ago

Hey there, I found these two books lsat summer when I wanted to know more about all this computer-science-y, data-structure-y stuff that I didn't know much about because of being self taught. Data Structures Succinctly 1 & 2. https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=data%20structures%20succinctly https://www.google.com/webhp?sourceid=chrome-instant&ion=1&e... Linking to Google search because they are behind a registration wall, but I haven't gotten an email from them yet. All the code examples are in C#, but they were both really good reads. I also found this a really good read for diving deep into how indexes work -- http://sql-performance-explained.com/ http://sql-performance-explained.com/

ufmace 12y ago
This site was linked somewhere here a while back - http://use-the-index-luke.com/ http://use-the-index-luke.com/ I learned a lot about how indexes work from it.
- Jgrubb 12y ago
  Yeah, that book I linked is the same guy as that site you linked. Good stuff.

grayclhn 12y ago

If you like this post, you should follow her twitter, where she's live-tweeting sqlite: https://twitter.com/b0rk https://twitter.com/b0rk