Hacker News new | past | comments | ask | show | jobs | submit login
How does SQLite work? Part 1: Pages (jvns.ca)
149 points by jvns on Sept 28, 2014 | hide | past | web | favorite | 18 comments

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.

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.


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/

This site was linked somewhere here a while back - http://use-the-index-luke.com/

I learned a lot about how indexes work from it.

Yeah, that book I linked is the same guy as that site you linked. Good stuff.

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

I have heard SQLite described as "alien technology".

Super fun blog way of looking at it!

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

btree is probably "binary tree".

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.

It's [B-Tree](http://en.wikipedia.org/wiki/B-tree) - a generalization of binary search tree.

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.

> 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.

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

They're aliens, who knows how they think? After all the Vogons are basically intergalactic bureaucrats.

Copyrights do expire, you know.

Not according to Disney.

Registration is open for Startup School 2019. Classes start July 22nd.

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