What Is a Database? Tables, SQL and Indexes Explained

In everyday life

When you press the order button in an online shop, the stock drops by one and one new order record is added. When you open a banking app, your current balance appears right away. Behind both, data is being stored in a database and fetched from it.

There is one inside your phone, too. It is a small database program called SQLite. According to its developers' official site, it is built into both Android phones and iPhones.

This article looks at how a database finds data among huge amounts in an instant. It also shows why we can trust it with records of money. Along the way, it explains terms from the official topic lists (syllabi) of two Japanese IT exams in plain words. These are IT Passport and the Fundamental Information Technology Engineer Examination.

Why isn't a spreadsheet file enough?

A spreadsheet program can also put data in a table. The trouble starts when the number of users and the amount of data grow. There are three main reasons.

The first is many people writing at the same time. A large online shop receives many orders every second. Suppose two people open the same file separately and edit it. The one who saves last may wipe out the other's changes.

The second is enforcing rules. Text ends up in the "quantity" field, or an order arrives for a member who does not exist. When people type data by hand, errors like these slip in. A database can reject data that breaks rules set in advance, right when it is entered.

The third is size and speed. One Excel sheet holds at most 1,048,576 rows (according to Microsoft's specifications). Large services handle many orders of magnitude more rows than that. Among them, they must find the one row they need without making users wait.

This work is taken on by dedicated software that manages the database. It is called a DBMS (database management system). Products include PostgreSQL, MySQL, SQLite and Oracle Database. Apps do not write data to files themselves. Instead, they ask the DBMS to "save this" or "find this."

How it works 1: tables, rows, columns and keys

The most widely used approach keeps data in the form of tables. This is called a relational database. Edgar Codd, a researcher at IBM, presented the idea in a 1970 paper.

The horizontal lines of a table are called rows, and the vertical ones are called columns. One row is one record (for example, one member), and the columns are its fields, such as name and address. Unlike in a spreadsheet, each column can have rules like "whole numbers only" or "may not be blank."

To pick out exactly one row, you choose a column in which no value appears twice, such as a member ID. This is called the primary key. Even if two members share the same name, the member ID keeps them apart.

The member_id column in the orders table points to the primary key of the members table. A column that points to another table's primary key like this is called a foreign key. If you try to add an order with a number that is not in the members table, the DBMS rejects it.

Why not write the member's name directly in the orders table? If you write the name on every order, a name change means fixing dozens of rows. Miss even one, and the data no longer agrees. Splitting tables so that each fact is written in only one place is a design step called normalization.

How it works 2: SQL describes what you want

The language for passing requests to a DBMS is SQL (read letter by letter, "S-Q-L"). It is defined in the international standard ISO/IEC 9075. Each product has small dialect differences, but the basic way of writing it is shared.

The three examples below are SQL for the tables in the figure above. The words are close to plain English, so reading them aloud tells you what they mean. The table and column names match the figure, with words joined by underscores (member_id).

SELECT means "pick and take out," FROM means "from which table," and WHERE means "the rows that meet which condition." In SQL you write only what you want, not the order in which to search. The DBMS decides how to search on its own, looking at things like the size of the tables.

Link the two tables by member ID, and you can answer questions that span both, such as "the items ordered by members in Osaka." Here, the foreign key is the marker that links them.

How it works 3: indexes narrow the search in one jump

Suppose you want the orders with member ID 457 from an orders table of 100 million rows. With no preparation, the DBMS has no choice but to check every row, starting from the first. If each row is 100 bytes, that is 10 GB to read. Even a fast SSD that reads about 7 GB per second in a continuous stream would need more than 1 second.

So you build a separate list in advance. It sorts the values of the column you search on, from smallest to largest, and notes where the rows with each value are. This is called an index. In many DBMSs you create one with a command called CREATE INDEX (one is made automatically for the primary key column). Once it exists, the DBMS uses it by itself whenever it judges it useful. It also updates the index by itself each time rows change.

When a DBMS moves data to and from an SSD or memory, it does not read and write one row at a time. It uses blocks of a fixed size, called "pages." A page is usually 8 KB in PostgreSQL and 16 KB in MySQL's standard storage engine (InnoDB).

With 100 million rows, the index list itself becomes huge. So the list is split into pages. On top go layers of guides that say "which page holds numbers up to what." The tree-shaped index made this way is called a B-tree. Bayer and McCreight published it in a 1972 paper.

As in the figure, the DBMS reads one page per level from the top and chooses which branch to follow. One page can hold hundreds of guides, so each level down narrows the range by a factor of several hundred. Suppose one page holds 300 guides. Then 3 levels can tell apart 300 × 300 × 300 = 27 million rows, and 4 levels can tell apart 8.1 billion. Even in a table of 100 million rows, reading about 4 pages tells you where the row is.

Now search the same 100 million rows with binary search, which halves the range each time. It takes at most 27 comparisons. But the places it compares start out far apart, so each comparison reads a different page. Under the same assumption of 300 entries per page, that comes to nearly 20 page reads. A B-tree compares hundreds of candidates at once within one page. This cuts the number of pages read from slow storage.

The indexes that PostgreSQL and MySQL (InnoDB) create by default also belong to the B-tree family. In practice they use improved forms such as the "B+ tree," which links the bottom-level pages side by side to make range searches easier.

However, an index is not always used. Suppose most rows in the table match the condition. Then reading the table from the start can be faster than using the index to fetch rows one by one. The DBMS estimates which is better and decides.

How it works 4: transactions, "all or nothing"

Imagine that person A sends 10,000 yen to person B. Inside the database, this takes two changes. One subtracts 10,000 yen from A's balance, and the other adds 10,000 yen to B's balance.

What if a power cut stops the server right after the first change? A's money has gone down, but it never reaches B, so 10,000 yen vanishes. To prevent this, the two changes must be handled as one set that cannot be split.

This set of operations is called a transaction. In PostgreSQL and some other systems, you start it with BEGIN, and writing COMMIT at the end makes the result final. If a problem occurs midway, ROLLBACK returns everything to the state before it started.

The four properties a transaction must keep are called the ACID properties, from the first letters of their English names. Theo Härder and Andreas Reuter coined the name in a 1983 paper. The table below sums up each one using the transfer example.

To protect isolation, the DBMS makes one of two operations wait for a while when both try to change the same row. It is like hanging an "in use" sign on the row, and it is called a lock. Thanks to this, even if two transfers take money from the same account at the same moment, the balance does not come out wrong.

But too much waiting slows everything down. So you can choose in the settings how strictly isolation is kept. This setting is called the isolation level.

Durability is protected by the order in which things are written. Before the DBMS changes the tables on the SSD, it writes "what will change, and how" in a separate record, called the log. It replies "complete" only after it confirms the log has been written to the SSD or similar storage. Even after a power cut, rereading the log at restart restores the confirmed changes.

Relational databases and NoSQL

Some databases do not use tables at all. They were built for data that does not fit a table shape, and for services of very large scale. The many kinds other than relational databases are grouped together as NoSQL (read "no S-Q-L").

A simple example is a type that just returns the contents when you give it a name. The name is called the "key" and the contents the "value," so this type is called a key-value store. The database does not care what the contents are.

Another type, the document store, keeps one record whole, like a single document. It can hold one member's name and that member's list of orders as one unit, without splitting them into tables.

Many NoSQL products spread data across many servers, and they are built to grow easily by adding machines. This approach is called scale-out. In exchange, they sometimes give up part of the strictness. For example, Amazon described a key-value store called Dynamo in a 2007 paper. Its top priority was never going down. Under some kinds of failure, it lets the contents of different servers disagree for a while.

It is less about which one is better than about using each where it fits. Relational databases are strong for data where mismatches are not allowed, such as money and stock. When you want many servers to handle a huge number of requests, NoSQL can be a better fit.

Where is a database actually kept?

In the end, a database's contents are files inside a server. Tables and indexes are written, as collections of pages, onto SSDs or HDDs, which keep data when the power is off.

But waiting for one read from an SSD takes about 0.1 milliseconds. That is about a thousand times longer than memory, at about 100 nanoseconds ("Memory vs Storage: What's the Difference?"). So the DBMS keeps copies of often-used pages in memory. According to the MySQL manual, a dedicated server often gives up to about 80% of its memory to this area. The upper levels of a B-tree are read again and again, so they tend to stay in memory. Often only the lower levels need a trip to the SSD.

Today, more and more databases are rented as a service from cloud providers. Even then, the data sits on the SSDs and other storage of servers in the provider's data centers ("What Is Cloud Computing?").

Common misconceptions

By the numbers

The B-tree and full-read figures are simplified estimates. The real number of levels depends on the key length and how full the pages are. The read time depends on whether a copy is already in memory.

Learn more

• Try it: the SQL practice tool, the binary search tree and heap visualizer and the RAID capacity calculator
• Compare in a table: relational database vs. NoSQL, inner join vs. outer join, SSD vs. HDD
• Terms for your next step: E-R diagram, third normal form, database view, two-phase locking, deadlock, SQL injection
• Read the basics: "Memory vs Storage: What's the Difference?", "What Is an Algorithm?", "What Is a Data Center?"