I've always been interested in how you can throw some SQL at at database, and it nearly instantaneously returns your results in an orderly manner without thinking about it as anything other than a black box.
What is really going on?
I'm pretty sure it has something to do with how values are laid out regularly in memory, similar to an array; but aside from that, I don't know much else.
How is SQL parsed in a manner to facilitate all of this?
The engine builds a such called query plan.
It's a set of algorithms used to return the sets that you described logically with an SQL query.
Almost each engine lets you see what query plan will it build for a certain query.
In MySQL and PostgreSQL, you prepend your query with the word EXPLAIN
In SQL Server, you run SET SHOWPLAN_TEXT ON before running the query or just press Ctrl-L in the Management Studio
In Oracle, you prepend the query with EXPLAIN PLAN FOR and then issue SELECT * FROM (dbms_xplan.display)
You may find interesting this article in my blog:
which addresses the same question.
You can read these books:
[1] H. Garcia-Molina, Database System Implementation, Prentice Hall, 2000
[2] R. Elmasri, S. B. Navathe, Fundamentals of Database Systems, The Benjamin/Cummings Publ. Comp., Inc, 1994
In a basic sense, for many RDBMS:
a) The syntax analysis stage takes input from the server setup (sockets, whatever) and turns this SQL into a valid AST or another intermediate form.
b) It then passes this information to a storage engine which turns this query description into a set of lookups on indexes, tables, partitions, replicated data and other elements that make up the semantics of storing the schema
c) The engine then returns a set of data which is then provided to the client in whatever form (XML, CSV, Client specific).
But there isn't one true answer. You will find similarities in indexing algorithms, distribution algorithms, caching, locking and other things ... but the main similarities is the language interface of the SQL language itself. Beyond there, they can be implemented in any way they wish ... providing their results meet the expected semantics of the input query.
Really RDBMs contain all kinds of structures from computer science ... and each has highly developed and specialized methods for turning the implied semantics of SQL into concrete storage.
Think of how different MySQL and Oracle are ... or PostgreSQL and Microsoft SQL. They all attempt to meet some kind of common SQL-like specification ... but how that specification is fulfilled is diverse.
Engines incorporate all kinds of exotica, specialist indexes to find datas physical location, caching systems and more.
There are tons of open source databases such as MySQL, PostgreSQL and search systems such as Sphinx you can have a look at their implementation. Open source is for learning as much as anything! Try and find a 'mentor' to guide you through the source.
I'm pretty sure it has something to do with how values are laid out regularly in memory, similar to an array; but aside from that, I don't know much else.
You might also want to look up articles on B+ Trees. That's the data structure main relational databases use.