Delete on MyISAM locks the table for reads and writes.
InnoDB takes increases space usage by 5x.
If a single thread accesses the database, then MyISAM is the ideal choice unless transaction support is required. Otherwise, use InnoDB for multithreaded access and row-level locking instead of table level locking.

What happens when alter is executed?

1. If a transaction is open on this thread, commit it.
2. Acquire a read lock for the table.
3. Make a temporary table with new structure
4. Copy the old table to the temporary table row by row changing the structure of the rows on the fly.
5. Rename the original table out of the way
6. Rename the temporary table to the original table name.
7. Drop the original table.
8. Release the read lock
9. alter can take a long time, from minutes to hours.

When a connection has a write lock, other connections can still read from the database. The connection can also write as many times as necessary before committing. Other connections cannot write and will deadlock, depending on the timeout.

ibdata1 for InnoDB databases cannot shrink. Instead, use innodb_file_per_table which creates one ibdata file per InnoDB table. Then ibd files can be deleted individually. Not sure, but it seems that you can delete the ibd file and the database will automatically rebuild it.

For order performance, see http://s.petrunia.net/blog/?p=24

From Common Questions:
Q: If I see "Using temporary; Using filesort" in the Extra column of EXPLAIN output, does that mean a temporary table is created on disk?
A:No. A disk-based table will only occur in the following situations:

• When the size of the implicitly created temporary table (from a GROUP BY or ORDER BY on a non-indexed column) is greater than both tmp_table_size and max_heap_table_size
• When there are any BLOB or TEXT fields in the SELECT expression
• When a full table scan occurs that exceeds the read_buffer_size variable (configured per connection thread)

These are the scenarios (off the top of my head) I can think of which cause disk-based temporary table creation. There could be a few more. By the way, the disk-based temporary table created is a MyISAM table. 

UTF8 Collation
utf8_bin: compare strings by the binary value of each character in the string
utf8_general_ci: compare strings using general language rules and using case-insensitive comparisons
utf8_general_cs: compare strings using general language rules and using case-sensitive comparisons

Oracle
Caution: text comparisons are case sensitive

Berkeley DB
Getting Started Guide is excellent. Berkeley DB collections seem better than custom extending Map (or other Collection) interface with a Berkeley DB backend.

Terrible delete performance. Doesn't scale beyond a certain limit. The database attempts to load as much as possible into memory and performs continuous garbage collection. The machine ends up being CPU and memory starved.