MyISAM 和 InnoDB 索引结构及其实现原理

1. 数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。

2. 索引的实现通常使用B_TREE。
   B_TREE索引加速了数据访问，因为存储引擎不会再去扫描整张表得到需要的数据;
   相反,它从根节点开始，根节点保存了子节点的指针，存储引擎会根据指针快速寻找数据。

3. MyISAM引擎 使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址.
   即:MyISAM索引文件和数据文件是分离的，MyISAM的索引文件仅仅保存数据记录的地址。
   MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，
   如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
   MyISAM的索引方式也叫做"非聚集"的。
   物理文件结构为：
   .frm文件：与表相关的元数据信息都存放在frm文件，包括表结构的定义信息等。
   .myd（mysql data）文件：myisam存储引擎专用，用于存储myisam表的数据
   .myi（mysql index）文件：myisam存储引擎专用，用于存储myisam表的索引相关信息

4. InnoDB引擎 也使用B+Tree作为索引结构，但是InnoDB的数据文件本身就是索引文件，叶节点data域保存了完整的数据记录。
   这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。这种索引叫做"聚焦索引"。
   InnoDB的辅助索引的data域存储相应记录主键的值而不是地址。
   换句话说，InnoDB的所有辅助索引都引用主键作为data域。
   聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引:
   首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
   InnoDB的索引实现后，不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
   在InnoDB中也不建议使用非单调的字段作为主键，
   因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，建议使用自增字段作为主键。
   物理文件结构为：
   .frm与表相关的元数据信息都存放在frm文件，包括表结构的定义信息等。
   .ibd文件和.ibdata文件：
   这两种文件都是存放innodb数据的文件，之所以用两种文件来存放innodb的数据，是因为innodb的数据存储方式能够通过配置来决定是使用共享表空间存放存储数据，还是用独享表空间存放存储数据。
   独享表空间存储方式使用.ibd文件，并且每个表一个ibd文件；
   共享表空间存储方式使用.ibdata文件，所有表共同使用一个ibdata文件；
   觉得使用哪种方式的参数在mysql的配置文件中 innodb_file_per_table；

MyISAM 和 InnoDB 索引结构及其实现原理