Good write up. Another excellent resource straight out of the UC Berkeley Database Group that I keep close by is "Architecture of a Database System"[1] by three researchers in the field. It is very readable.<p>[1] <a href="http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf" rel="nofollow">http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf</a>
Good overview of traditional OLTP architectures. As complicated as they look from the article, it is just scratching the surface of a sophisticated implementation. There are many internals common to more advanced designs that are not even mentioned, and the article is already quite long!<p>The thing I love most about database engines is that there is probably more hardcore computer science per line of code than any other software system of similar scope. It is a very rich ecosystem for an algorithms and data structures geek.
Be careful with theoretical asymptotic complexity (big O) related to execution time. E.g. if your algorithm time complexity is O(1), but internally calls a higher complexity function, e.g. malloc(), implemented with higher complexity, e.g. O(log n), your algorithm time complexity would be O(log n) and not O(1). It could be even worse: <i>on average</i> or <i>typical</i> constant time algorithm could be in reality an O(n) one: e.g. case of hash table reindexation (that's the reason of why many big data structures, including most SQL databases, requiring real time behavior, are implemented as trees, tree hierarchies/division/clustering, instead of big hash tables).
Because I am interested in databases, I found the Se-radio's 2013 interview with Michael Stonebreaker [1] interesting, particularly in regard to traditional database design and more recent ideas:<p><a href="http://www.se-radio.net/2013/12/episode-199-michael-stonebraker/" rel="nofollow">http://www.se-radio.net/2013/12/episode-199-michael-stonebra...</a><p>[1]: <a href="http://www.theregister.co.uk/2015/03/25/mike_stonebraker_wins_turing_award/" rel="nofollow">http://www.theregister.co.uk/2015/03/25/mike_stonebraker_win...</a>
> When it comes to relational databases, I can’t help thinking that something is missing. They’re used everywhere. There are many different databases: from the small and useful SQLite to the powerful Teradata. But, there are only a few articles that explain how a database works.<p>That's because the inner workings are really old, as in: emerged before blogging etc. was popular, hell before the internet was invented.<p>In the 'before/early internet days', we read books like 'An introduction to Database Systems' by C.J. Date. (I had to blow the dust off my copy to read the exact title ;)), which are more in depth than this article, but I like the article better, because it's more to the point and easier to understand. Well done!
Not that Cassandra and Hadoop don't have a place. But because NO-SQL is hot I see lots of young coders (I'm and old DBA) try to turn document store systems into relational databases. They should all be made to read this post.
This is also a pretty accessible quick intro to complexity and data structures, nicely done. Definitely the sort of thing I would include as further reading in a beginner course -- some beginners love to understand "why" and this post answers pretty much all the "why" possible.
I decided to spend some time digging into SQLite. I highly recommend the overviews of their architecture and the details about each part of the puzzle.<p>It's really understandable, very straight forward, even if a lot of it refers to SQLite v2, it still seems very relevant.<p><a href="http://www.sqlite.org/arch.html" rel="nofollow">http://www.sqlite.org/arch.html</a>
Great Article , I wish a book was written where a simple database with a query language was implemented from start to finish , even a nosql one, I always wanted to implement my own.
> Nowadays, many developers don’t care about time complexity … and they’re right!<p>That's a pretty bold statement...<p>Very thorough explanations though!