MySql och index

Jag håller på en del med utveckling i PHP och tycker mig ha ganska bra koll på hur man bygger upp en effektiv databasstruktur. Det som jag har inte riktigt har full kontroll över är hur jag använder index på bästa sätt.
Låt oss säga att jag skall bygga en applikation där användare kan betygsätta skivor och jag har en databasstruktur som ser ut på följande sätt:

CREATE TABLE `records` (
`id` int( 11 ) NOT NULL AUTO_INCREMENT ,
`name` varchar( 255 ) default NULL ,
`artist_id` int( 11 ) unsigned NOT NULL default '0',
`release_year` varchar( 4 ) default NULL ,
`songs` text,
`created_date` int( 11 ) unsigned NOT NULL default '0',
`created_user_id` int( 11 ) unsigned NOT NULL default '0',
PRIMARY KEY ( `id` ) ,
) TYPE = MYISAM

CREATE TABLE `users` (
`id` int( 11 ) NOT NULL AUTO_INCREMENT ,
`username` varchar( 255 ) default NULL ,
`password` varchar( 255 ) default NULL ,
`created_date` int( 11 ) unsigned NOT NULL default '0',
`modified_date` int( 11 ) unsigned NOT NULL default '0',
`online` int( 11 ) unsigned NOT NULL default '0',
`record_grades` int( 11 ) unsigned NOT NULL default '0',
`disabled` tinyint( 1 ) unsigned NOT NULL default '0',
`banned` tinyint( 1 ) unsigned NOT NULL default '0',
PRIMARY KEY ( `id` )
) TYPE = MYISAM

CREATE TABLE `record_grades` (
`record_id` int( 11 ) unsigned NOT NULL default '0',
`grade` tinyint( 2 ) unsigned NOT NULL default '0',
`user_id` int( 11 ) unsigned NOT NULL default '0',
`timestamp` int( 11 ) unsigned NOT NULL default '0',
) TYPE = MYISAM ;

Frågan är alltså vilka fält som bör ha ett index. Min gissning är att tabellen "records" bör ha ett på artist_id eftersom man ofta kommer att fråga efter skivor gjorda av en viss artist.
Det jag är mest tveksam till är huruvida jag skall göra några index på "record_grades". Det kommer att göras en hel del frågor både med record_id och user_id efter WHERE i SQL-satsen. Det är ju också den tabellen som kommer att bli störst, frågan är hur mycket snabbare en sökning blir och om det är värt det med tanke på hur mycket större plats tabellen kommer att ta.

Sen har jag sett att man kan göra ett index på två tabeller samtidigt, vad innebär det? Är det det jag skall göra om jag gör index på de två fälten i record_grades?

Hur brukar ni använda index? Är det någon som har några tips på artiklar om detta på nätet? Är tacksam för all hjälp och synpunkter jag kan få.

Vet inte riktigt varför jag gör det, har blivit en vana bara. Jag sparar ner datum som Unix-time och ser inga problem med att använda int. Kanske skall ta och göra som du säger i alla fall...
Ingenting angående index?

Ok, skall ta och gräva lite i manualen. De gånger jag varit inne på mysql.com och läst har jag tyckt att det har varit lite svårt att få en riktig översikt över den. Nåja, jag kanske bara är ovan. Tack för hjälpen i alla fall.