A database, simply put, is a collection of organized data. An example would be card catalogs at libraries (originally on a collection of 3x5" cards, now usually on computers). Another example would be a collection of all the names and addresses of the voting population of Los Angeles.
Data in a database is organized by means of a key which allows sorting the data for quick lookup and retrieval of the information. For instance, a library's card catalog can be organized by title, or by author and title. In the first case, the title is the key. In the second case, the combined author and title are the key. Each card represents a record of information, which contains fields of information related to the key for that record (such as the publisher, copyright year, and a brief description, in addition to the author and title). Because a physical database can only be effectively sorted for one key, a card catalog had to be duplicated, with each duplicate being sorted differently (one by author name, one by title, etc.). In database terminology, each different sorted collection is called a table, and the collection of all related tables is collectively called a database.
The size of the database is the number of records it contains. This can be from 1 to billions of records. Implementation of a database in software provides several advantages over a physical database: 1) much smaller physical size, especially for large databases, 2) much faster lookup of information, 3) the ability to have multiple keys applied to the same data, rather than a separate table for the way each table is keyed, 4) the ability to quickly apply changes across multiple (or all) records.
Databases are organized in different ways, internally.
Network databases have a flexible organization in which the records can vary in layout. The relationship between the records could be described as a directed graph (Network).
Object databases use an object model to represent records of data. Versant is an example of an object oriented database. OODB-s offer a different strategy than relational db-s that some claim can lead to much greater speed. The market now seems to favor relational databases currently and only time will tell if OODB-s catch on.
The most commonly used organization is relational, in which the data in the tables are organized as rows (records) and columns (fields). Relational databases differ from other database organizations in that each row has the exact same fields as every other row for a given table, although some fields may be unused for some rows. Keys are defined as being one or more columns and data lookups using keys is much faster than lookups based on non-key fields. Fields in one table can be associated with related fields in other tables, hence the name "relational", and data can be looked up by simple join operations that returns records from several tables based on these related fields.
Relational databases have become popular due to high speed.
SQL created by EF Codd at IBM (see his paper the relational model) is Structured Query Language, a language for manipulating large data tables within a database. Most relational databases support the use of SQL. Users ask for the data they write a "query" using SQL and the database quickly returns the data.
There are some big database vendors in the software business such as Oracle, IBM's DB2, SAP, SYBASE, Microsoft SQL Server, Versant as well as some free software alternatives such as postgresql, firebird, and MySQL.