CREATE TABLE People (

   last_name varchar(50)    not null,

   first_name varchar(50)    not null,

   dob        date           not null,

   gender     enum('m', 'f') not null,

   key(last_name, first_name, dob)

);

 其索引包含表中每一行的last_name、first_name和dob列。其結(jié)構(gòu)大致如下：

函數(shù)f( )

f('Arjen') = 2323

f('Baron') = 7437

f('Peter') = 8784

f('Vadim') = 2458

 Slots是有序的，但是記錄不是有序的。當(dāng)你執(zhí)行
mysql> SELECT lname FROM testhash WHERE fname='Peter';
MySQL會(huì)計(jì)算’Peter’的hash值，然后通過它來查詢索引的行指針。因?yàn)閒('Peter') = 8784，MySQL會(huì)在索引中查找8784，得到指向記錄3的指針。
因?yàn)樗饕约簝H僅存儲(chǔ)很短的值，所以，索引非常緊湊。Hash值不取決于列的數(shù)據(jù)類型，一個(gè)TINYINT列的索引與一個(gè)長(zhǎng)字符串列的索引一樣大。
 
Hash索引有以下一些限制：
(1)由于索引僅包含hash code和記錄指針，所以，MySQL不能通過使用索引避免讀取記錄。但是訪問內(nèi)存中的記錄是非常迅速的，不會(huì)對(duì)性造成太大的影響。
(2)不能使用hash索引排序。
(3)Hash索引不支持鍵的部分匹配，因?yàn)槭峭ㄟ^整個(gè)索引值來計(jì)算hash值的。
(4)Hash索引只支持等值比較，例如使用=，IN( )和<=>。對(duì)于WHERE price>100并不能加速查詢。
2.1.3、空間(R-Tree)索引
MyISAM支持空間索引，主要用于地理空間數(shù)據(jù)類型，例如GEOMETRY。
2.1.4、全文(Full-text)索引
全文索引是MyISAM的一個(gè)特殊索引類型，主要用于全文檢索。
 

3、高性能的索引策略
3.1、聚簇索引(Clustered Indexes)
聚簇索引保證關(guān)鍵字的值相近的元組存儲(chǔ)的物理位置也相同（所以字符串類型不宜建立聚簇索引，特別是隨機(jī)字符串，會(huì)使得系統(tǒng)進(jìn)行大量的移動(dòng)操作），且一個(gè)表只能有一個(gè)聚簇索引。因?yàn)橛纱鎯?chǔ)引擎實(shí)現(xiàn)索引，所以，并不是所有的引擎都支持聚簇索引。目前，只有solidDB和InnoDB支持。
聚簇索引的結(jié)構(gòu)大致如下：

CREATE TABLE layout_test (

   col1 int NOT NULL,

   col2 int NOT NULL,

   PRIMARY KEY(col1),

   KEY(col2)

);

 假設(shè)主鍵的值位于1---10,000之間，且按隨機(jī)順序插入，然后用OPTIMIZE TABLE進(jìn)行優(yōu)化。col2隨機(jī)賦予1---100之間的值，所以會(huì)存在許多重復(fù)的值。
(1)    MyISAM的數(shù)據(jù)布局
其布局十分簡(jiǎn)單，MyISAM按照插入的順序在磁盤上存儲(chǔ)數(shù)據(jù)，如下：

 注：MyISAM不支持聚簇索引，索引中每一個(gè)葉子節(jié)點(diǎn)僅僅包含行號(hào)(row number)，且葉子節(jié)點(diǎn)按照col1的順序存儲(chǔ)。
來看看col2的索引結(jié)構(gòu)：

 注：聚簇索引中的每個(gè)葉子節(jié)點(diǎn)包含primary key的值，事務(wù)ID和回滾指針(rollback pointer)&mdash;&mdash;用于事務(wù)和MVCC，和余下的列(如col2)。

相對(duì)于MyISAM，二級(jí)索引與聚簇索引有很大的不同。InnoDB的二級(jí)索引的葉子包含primary key的值，而不是行指針(row pointers)，這減小了移動(dòng)數(shù)據(jù)或者數(shù)據(jù)頁面分裂時(shí)維護(hù)二級(jí)索引的開銷，因?yàn)镮nnoDB不需要更新索引的行指針。其結(jié)構(gòu)大致如下：

 3.1.2、按primary key的順序插入行(InnoDB)

如果你用InnoDB，而且不需要特殊的聚簇索引，一個(gè)好的做法就是使用代理主鍵(surrogate key)&mdash;&mdash;獨(dú)立于你的應(yīng)用中的數(shù)據(jù)。最簡(jiǎn)單的做法就是使用一個(gè)AUTO_INCREMENT的列，這會(huì)保證記錄按照順序插入，而且能提高使用primary key進(jìn)行連接的查詢的性能。應(yīng)該盡量避免隨機(jī)的聚簇主鍵，例如，字符串主鍵就是一個(gè)不好的選擇，它使得插入操作變得隨機(jī)。

 3.2、覆蓋索引(Covering Indexes)
如果索引包含滿足查詢的所有數(shù)據(jù)，就稱為覆蓋索引。覆蓋索引是一種非常強(qiáng)大的工具，能大大提高查詢性能。只需要讀取索引而不用讀取數(shù)據(jù)有以下一些優(yōu)點(diǎn)：
(1)索引項(xiàng)通常比記錄要小，所以MySQL訪問更少的數(shù)據(jù)；
(2)索引都按值的大小順序存儲(chǔ)，相對(duì)于隨機(jī)訪問記錄，需要更少的I/O；
(3)大多數(shù)據(jù)引擎能更好的緩存索引。比如MyISAM只緩存索引。
(4)覆蓋索引對(duì)于InnoDB表尤其有用，因?yàn)镮nnoDB使用聚集索引組織數(shù)據(jù)，如果二級(jí)索引中包含查詢所需的數(shù)據(jù)，就不再需要在聚集索引中查找了。
覆蓋索引不能是任何索引，只有B-TREE索引存儲(chǔ)相應(yīng)的值。而且不同的存儲(chǔ)引擎實(shí)現(xiàn)覆蓋索引的方式都不同，并不是所有存儲(chǔ)引擎都支持覆蓋索引(Memory和Falcon就不支持)。
對(duì)于索引覆蓋查詢(index-covered query)，使用EXPLAIN時(shí)，可以在Extra一列中看到&ldquo;Using index&rdquo;。例如，在sakila的inventory表中，有一個(gè)組合索引(store_id,film_id)，對(duì)于只需要訪問這兩列的查詢，MySQL就可以使用索引，如下：

*************************** 1. row ***************************

           id: 1

 select_type: SIMPLE

        table: inventory

         type: index

possible_keys: NULL

          key: idx_store_id_film_id

      key_len: 3

          ref: NULL

         rows: 5007

        Extra: Using index

1 row in set (0.17 sec)

在大多數(shù)引擎中，只有當(dāng)查詢語句所訪問的列是索引的一部分時(shí)，索引才會(huì)覆蓋。但是，InnoDB不限于此，InnoDB的二級(jí)索引在葉子節(jié)點(diǎn)中存儲(chǔ)了primary key的值。因此，sakila.actor表使用InnoDB，而且對(duì)于是last_name上有索引，所以，索引能覆蓋那些訪問actor_id的查詢，如：

    -> FROM sakila.actor WHERE last_name = 'HOPPER'\G

*************************** 1. row ***************************

           id: 1

 select_type: SIMPLE

        table: actor

         type: ref

possible_keys: idx_actor_last_name

          key: idx_actor_last_name

      key_len: 137

          ref: const

         rows: 2

        Extra: Using where; Using index

3.3、利用索引進(jìn)行排序
MySQL中，有兩種方式生成有序結(jié)果集：一是使用filesort，二是按索引順序掃描。利用索引進(jìn)行排序操作是非?？斓?，而且可以利用同一索引同時(shí)進(jìn)行查找和排序操作。當(dāng)索引的順序與ORDER BY中的列順序相同且所有的列是同一方向(全部升序或者全部降序)時(shí)，可以使用索引來排序。如果查詢是連接多個(gè)表，僅當(dāng)ORDER BY中的所有列都是第一個(gè)表的列時(shí)才會(huì)使用索引。其它情況都會(huì)使用filesort。

password        varchar(16) NOT NULL DEFAULT '',

PRIMARY KEY(actor_id),

 KEY     (name)

) ENGINE=InnoDB

insert into actor(name,password) values('cat01','1234567');

insert into actor(name,password) values('cat02','1234567');

insert into actor(name,password) values('ddddd','1234567');

insert into actor(name,password) values('aaaaa','1234567');

*************************** 1. row ***************************

           id: 1

 select_type: SIMPLE

        table: actor

         type: index

possible_keys: NULL

          key: PRIMARY

      key_len: 4

          ref: NULL

         rows: 4

        Extra: 

mysql> explain select actor_id from actor order by password \G

*************************** 1. row ***************************

           id: 1

 select_type: SIMPLE

        table: actor

         type: ALL

possible_keys: NULL

          key: NULL

      key_len: NULL

          ref: NULL

         rows: 4

        Extra: 

mysql> explain select actor_id from actor order by name \G

*************************** 1. row ***************************

           id: 1

 select_type: SIMPLE

        table: actor

         type: index

possible_keys: NULL

          key: name

      key_len: 18

          ref: NULL

         rows: 4

        Extra: 

(1)兩遍掃描算法(Two passes)
實(shí)現(xiàn)方式是先將須要排序的字段和可以直接定位到相關(guān)行數(shù)據(jù)的指針信息取出，然后在設(shè)定的內(nèi)存（通過參數(shù)sort_buffer_size設(shè)定）中進(jìn)行排序，完成排序之后再次通過行指針信息取出所需的Columns。
注：該算法是4.1之前采用的算法，它需要兩次訪問數(shù)據(jù)，尤其是第二次讀取操作會(huì)導(dǎo)致大量的隨機(jī)I/O操作。另一方面，內(nèi)存開銷較小。
(3)    一次掃描算法(single pass)
該算法一次性將所需的Columns全部取出，在內(nèi)存中排序后直接將結(jié)果輸出。
注：從 MySQL 4.1 版本開始使用該算法。它減少了I/O的次數(shù)，效率較高，但是內(nèi)存開銷也較大。如果我們將并不需要的Columns也取出來，就會(huì)極大地浪費(fèi)排序過程所需要的內(nèi)存。在 MySQL 4.1 之后的版本中，可以通過設(shè)置 max_length_for_sort_data 參數(shù)來控制 MySQL 選擇第一種排序算法還是第二種。當(dāng)取出的所有大字段總大小大于 max_length_for_sort_data 的設(shè)置時(shí)，MySQL 就會(huì)選擇使用第一種排序算法，反之，則會(huì)選擇第二種。為了盡可能地提高排序性能，我們自然更希望使用第二種排序算法，所以在 Query 中僅僅取出需要的 Columns 是非常有必要的。

當(dāng)對(duì)連接操作進(jìn)行排序時(shí)，如果ORDER BY僅僅引用第一個(gè)表的列，MySQL對(duì)該表進(jìn)行filesort操作，然后進(jìn)行連接處理，此時(shí)，EXPLAIN輸出&ldquo;Using filesort&rdquo;；否則，MySQL必須將查詢的結(jié)果集生成一個(gè)臨時(shí)表，在連接完成之后進(jìn)行filesort操作，此時(shí)，EXPLAIN輸出&ldquo;Using temporary;Using filesort&rdquo;。

3.4、索引與加鎖
索引對(duì)于InnoDB非常重要，因?yàn)樗梢宰尣樵冩i更少的元組。這點(diǎn)十分重要，因?yàn)镸ySQL 5.0中，InnoDB直到事務(wù)提交時(shí)才會(huì)解鎖。有兩個(gè)方面的原因：首先，即使InnoDB行級(jí)鎖的開銷非常高效，內(nèi)存開銷也較小，但不管怎么樣，還是存在開銷。其次，對(duì)不需要的元組的加鎖，會(huì)增加鎖的開銷，降低并發(fā)性。
InnoDB僅對(duì)需要訪問的元組加鎖，而索引能夠減少InnoDB訪問的元組數(shù)。但是，只有在存儲(chǔ)引擎層過濾掉那些不需要的數(shù)據(jù)才能達(dá)到這種目的。一旦索引不允許InnoDB那樣做（即達(dá)不到過濾的目的），MySQL服務(wù)器只能對(duì)InnoDB返回的數(shù)據(jù)進(jìn)行WHERE操作，此時(shí)，已經(jīng)無法避免對(duì)那些元組加鎖了：InnoDB已經(jīng)鎖住那些元組，服務(wù)器無法解鎖了。
來看個(gè)例子：

password        varchar(16) NOT NULL DEFAULT '',

PRIMARY KEY(actor_id),

 KEY     (name)

) ENGINE=InnoDB

insert into actor(name,password) values('cat01','1234567');

insert into actor(name,password) values('cat02','1234567');

insert into actor(name,password) values('ddddd','1234567');

insert into actor(name,password) values('aaaaa','1234567');

    -> WHERE actor_id < 4 AND actor_id <> 1 FOR UPDATE \G

*************************** 1. row ***************************

           id: 1

 select_type: SIMPLE

        table: actor

         type: index

possible_keys: PRIMARY

          key: PRIMARY

      key_len: 4

          ref: NULL

         rows: 4

        Extra: Using where; Using index

1 row in set (0.00 sec)

mysql>

為了證明row 1已經(jīng)被鎖住，我們另外建一個(gè)連接，執(zhí)行如下操作：

 該查詢會(huì)被掛起，直到第一個(gè)連接的事務(wù)提交釋放鎖時(shí)，才會(huì)執(zhí)行（這種行為對(duì)于基于語句的復(fù)制(statement-based replication)是必要的）。
如上所示，當(dāng)使用索引時(shí)，InnoDB會(huì)鎖住它不需要的元組。更糟糕的是，如果查詢不能使用索引，MySQL會(huì)進(jìn)行全表掃描，并鎖住每一個(gè)元組，不管是否真正需要。