InnoDB存储引擎之 —— 索引算法（一）（草稿...）

InnoDB 存储引擎表示索引组织表，表中数据按照主键顺序存放。
索引应该在一开始开发的时候就进行添加。
索引太少，影响性能。索引太多，也影响性能，比如太多索引会导致磁盘使用率非常高。

索引的类型

1. B+ 树索引
   传统意义上的索引，最常用，最有效。
   B+ 树索引不能定位到具体的行，只能定位到具体的页，然后把页读到内存中查找满足条件的行。
2. 全文索引
3. 哈希索引
   InnoDB 的哈希索引是自适应的，会根据表的使用情况自动为表生成，不能认为干预。

背景知识：
二分查找：
第一个二分查找在1946年出现，第一个正确的二分查找法在1962年才出现。

B+树：
省略

B+树索引：

1. 聚集索引(clustered index)
   根据每张表的主键构建的一颗B+树(一张表只能有一个聚集索引)，叶子节点存放的是一整行的信息。聚集索引的叶子也称作数据页，每个数据页通过双向链表链接。

2. 辅助索引(secondary index)
   叶子节点存放的不是一整行的信息。