Yes and no.
An "array" in a programming language does some trivial address arithmetic to quickly locate the Nth entry in the array.
In MySQL, most indexes are built as B+Trees. (See Wikipedia) This structure is more complex than an array, but still the best available.
WHERE id=2 requires drilling down a "tree" of nodes to locate the item with "2" in the "id" column.
A BTree has several advantages over a simple array. And these advantages are necessary for the generality of database operations.
- Database tables are designed to handle an arbitrarily large number of items. Arrays are limited to what can fit in RAM. This effectively prevents the address arithmetic of arrays, and forces some other implementation.
- You can
DELETE * FROM t WHERE id=2. (Arrays don't allow holes; BTrees do.) Note that it prevents the use of "address arithmetic" to locate a record.
- A BTree index can use a string for lookup --
WHERE name = 'Venus'. And this works as easily and almost as fast as using numbers.
- Since BTrees are "blocks"; they get scattered around and they could become empty. This leads to the overhead of maintenance of the tree. Don't worry about this; BTrees are still very fast, on average.
- "Clustering" in this context implies that ids 1,2,3,... are "consecutive" and "adjacent" in some sense. (Or "1,3,...", if id=2 has been deleted.) In practice, there are about 100 consecutive values sitting in one B+Tree block. This allows for "range" to be very efficient. Example:
WHERE name BETWEEN 'Mars' AND 'Venus' would be store alphabetically.
- When a 'range' query runs off the end of a B+Tree block, the next block is linked from it. (This is the "+".)
- Technically, array lookup is O(1) and a BTree lookup is O(logN). But the log is not that big a number -- A BTree for a million rows is about 3 levels deep; for a trillion rows, only about 6 levels deep. That is, looking up a row in a trillion-row table is only about twice as slow as in a million-row table.
- MySQL (InnoDB specifically) requires a unique
PRIMARY KEY and clusters it with the data.
- Hence, a lookup by the PK (
WHERE id=2, if
id is the PK) is one drill-down of one BTree to get to the entire row.
- A secondary index (not the PK) is implemented as a B+Tree with the key column(s) plus the column(s) of the PK.
- Hence, lookup by a secondary key (
SELECT * FROM t WHERE name='Venus' with
INDEX(name)) is a little more complex. First drill down the
name index to find the
id, then drill down the PK+data BTree to find the entire row.
- Prevention of duplicates -- This happens when
UPDATEing a row. Effectively, it looks up the row via the
PRIMARY KEY (if given -- cf
AUTO_INCREMENT) and via every
UNIQUE index. If any of those are a match, you get an error (unless doing
INSERT IGNORE). Otherwise, the PK's BTree and the Unique BTrees are poised to take the new/modified row. Dealing with potential dups is not free, but cheap.
- For a
BETWEEN, the first row is accessed (O(logN)), then each subsequent row is O(1).
So, yes, an array lookup takes nanoseconds, which is faster than a database lookup, which takes microseconds (if cached in RAM), or milliseconds (if I/O is needed). That is the price you have to pay for unlimited size and many more features.