InnoDB is one of the most complex storage engines currently present in MySQL. It supports transactions, multi-versioning, row-level locks, and foreign keys. It has an extensive system for managing I/O and memory. It has internal mechanisms for deadlock detection, and performs a quick and reliable crash recovery. It implements a number of algorithms to overcome the performance limitations of traditional databases that support transactions.
Unlike MyISAM, which always stores its data in files, InnoDB uses tablespaces. A table space can be stored in a file or on a raw partition. All tables may be stored in one common tablespace, or every table may have its own tablespace.
The data is stored in a special structure called a clustered index, which is a B-tree with the primary key acting as the key value, and the actual record (rather than a pointer) in the data part. Thus, each InnoDB table must have a primary key. If one is not supplied, a special row ID column not normally visible to the user is added to act as a primary key. A secondary key will store the value of the primary key that identifies the record. The B-tree code can be found in innobase/btr/btr0btr.c.
Both primary and secondary keys are stored in a B-tree on disk. However, when buffering the index page, InnoDB will build an adaptive hash index in memory to speed up the index lookups for the cached page. The code that deals with InnoDB adaptive hashing can be found in storage/innobase/ha/ha0ha.c.
While MyISAM buffers ...