让我们来看看
索引设计和工作原理
索引的设计和工作原理。 要创建高性能索引，首先需要知道什么是索引。 在维基百科中，数据库索引是一种数据结构，它以额外的写入和存储空间为代价加快了数据库表上的数据检索操作。 简单来说，索引就像书的目录一样，可以从书中的页码中快速找到所需的内容。MySQL公式索引(Index )的定义是存储引擎用于快速查找记录的数据结构。
索引是物理数据页，数据库页大小(Page Size )决定了一页可以存储的索引行数和指定大小的索引所需的页数。
索引可以加快搜索，但插入、删除和更新索引列的速度也会降低，从而导致索引维护成本增加。 关于索引的理论知识有二分搜索法、qjdmf表和b树。
二分查找法
二分搜索法也称为折半搜索法，是在规则数组内搜索指定数据的搜索算法。 下图是维基百科二分搜索法的定义。 优点是等效查询、范围查询性能优异，但缺点是更新数据、添加数据、删除数据的维护成本高。举个例子，顺序排列[1-71]有17个值。 也就是说，在顺序排列[A0-A16]中想找到Target(7所在的位置时，首先将下标l定为0，下标r定为16，下标m定为floor [(L R )/2]，下面取整数。
如果首先查询下标L=0，R=16，m=floor[(0 16 )/2]=8，则A8的值为14，如下图所示。 因为a8(14 ) target(7)被设定为R=m-1=7。
如下图所示，第二次查询的下标L=0，R=7，m=floor[(0 7 )/2]=3取得A3的值为6，a3(6) Target(7)7)取得下标L=m 1=4
如下图所示，第三次查询的后缀为L=4，R=7，m=floor[(4(7)/2 ) ]=5，所得到的A5的值为8，A5)8) Target(7)7)为后缀r
第四个查询的下标为L=4，R=4，m=floor[(4(4)/2 ) ]=4，得到的A4的值为7，a4(7)=Target(7)，查询结束如下图所示。
此次查询经过4次二分搜索找到目标数据7，如果查询中出现下标LR，则表示目标元素不在有序数组内，结束查询。
二分搜索是索引实现的理论基础，有助于下一步索引学习。
众所周知，
索引原理
数据库查询是数据库的核心功能，而索引是加快查询的重要技术手段。 索引数据结构选择的本质是结合当前数据读写的硬件环境选择优良的数据结构进行数据的存储和扫描，数据库中的大部分索引都是通过B Tree实现的。 当然也和其他数据结构有关。 除了b树索引外，MySQL还需要关注散列索引。然后，我们将逐一学习散列索引和B Tree索引。 因为后面的大部分内容都是关于b树的，所以为了使b树的内容更一致，我们先来谈谈散列索引。
Hash 索引
qjdmf表是数据库内qjdmf索引的基础，是基于键值key、value存储数据的结构。 简单地说，qjdmf表是使用qjdmf函数将索引列计算为桶或槽的数组，实际的存储根据qjdmf函数将key换算为确定的存储位置，并将value存储在该数组位置。 访问时，只需输入想要查找的密钥，即可通过qjdmf函数计算求出确定的存储位置，读取数据。如下图所示，将名称设为key，用qjdmf函数计算名称字段的数据，得到dzdlz，与桶和槽的排列并存，同时将指向实际数据行的指针作为value进行存储，制作qjdmf表。
>接下来我们从qjdmf索引如何实现、Hash 碰撞处理、MySQL 如何使用 Hash，三个方面学习qjdmf索引。
首先讲解qjdmf索引是如何实现的？数据库中qjdmf索引是基于qjdmf表实现的，对于qjdmf索引列的数据通过 Hash 算法计算，得到对应索引列的dzdlz形成qjdmf表，由dzdlz及dzdlz指向的真实数据行的指针组成了qjdmf索引。qjdmf索引的应用场景是只在对qjdmf索引列的等值查询才有效。
如下图所示，根据表中的 name 字段构建 Hash 索引，通过 Hash 算法对每一行 name 字段的数据进行计算，得出 Hash 码。由 Hash 码及 Hash 码指向真实数据行的指针组成了qjdmf索引。
因为qjdmf索引只存储qjdmf值和行指针，不存储实际字段值，所以其结构紧凑，查询速度也非常快，在无qjdmf冲突的场景下访问qjdmf索引一次即可命中。但是qjdmf索引只适用于等值查询，包括 =、IN()、<=> （安全等于， select null <=> null 和 select null=null 是不一样的结果) ，不支持范围查询。
另外，qjdmf索引的性能跟qjdmf冲突数量成反比，qjdmf冲突越多其维护代价越大性能越低。
接下来我们看看 Hash 碰撞如何处理？Hash 碰撞是指不同索引列值计算出相同的dzdlz，如上图所示， 表中 name 字段为 John Smith 和 Sandra Dee 两个不同值根据 Hash 算法计算出来的dzdlz都是 152，这就表示出现了 Hash 碰撞。 对于 Hash 碰撞通用的处理方法是使用链表，将 Hash 冲突碰撞的元素形成一个链表，发生冲突时在链表上进行二次遍历找到数据。
Hash 碰撞跟选择的 Hash 算法有关系，为了减少 Hash 碰撞的概率，优先选择避免 Hash 冲突的 Hash 算法，例如，使用 Percona Server 的函数 FNV64() ，其qjdmf值为 64 位，出现 Hash 冲突的概率要比 CRC32 小很多。其次是考虑性能，优先选择数字类型的 Hash 算法，因为字符串类型的 Hash 算法不仅浪费空间而且不方便进行比较。常见的 CRC32、SHA1 和 MD5 Hash 函数生成的返回值如下图所示。
综合建议 Hash 算法使用优先级为：FNV64 > CRC32 （大数据量下 Hash 冲突概率较大）> MD5 > SHA1。
最后再看看，MySQL 中如何使用 Hash 索引？在 MySQL 中主要是分为 Memory 存储引擎原生支持的 Hash 索引 、InnoDB 自适应qjdmf索引及 NDB 集群的qjdmf索引3类。
Memory 存储引擎原生支持的 Hash 索引，如上图所示，Memory 存储引擎创建表时即可原生显式创建并使用 Hash 索引。
相比 InnoDB，虽然不能原生显示创建 Hash 索引，但是可以伪造qjdmf索引来加速定值查询的性能。例如为超长文本（如网站 URL）进行 Hash 计算后的字段 url_hash 创建 B+Tree 索引，获得 Hash 索引的功能。
关于qjdmf索引，InnoDB 提供了 InnoDB 自适应qjdmf索引的强大功能，接下来重点描述 InnoDB 自适应qjdmf索引。
InnoDB 自适应qjdmf索引是为了提升查询效率，InnoDB 存储引擎会监控表上各个索引页的查询，当 InnoDB 注意到某些索引值访问非常频繁时，会在内存中基于 B+Tree 索引再创建一个qjdmf索引，使得内存中的 B+Tree 索引具备qjdmf索引的功能，即能够快速定值访问频繁访问的索引页。
B+Tree 索引
在数据库中大部分索引都是通过 B+Tree 来实现的。 对于 B+Tree 具体的定义可以参考《数据结构》等相关书籍。 在 MySQL 数据库中讨论索引时，如果没有明确指定类型，则默认是指使用 B+Tree 数据结构进行存储，其说法等价于 B+Tree、B-Tree、BTREE（看到创建索引语句为 BTREE 也不要惊讶，等同于 B+Tree）。
如下图所示为一个简单的、标准的 B+tree，每个节点有 K 个键值和 K+1 个指针。
对于 MySQL 存储引擎而言，其实际使用的 B+Tree 索引是为了满足数据读写性能，以及适配磁盘访问模式优化后的数据结构，每一个叶子节点都包含指向下一个叶子节点的指针。
在 MySQL 中，索引是在存储引擎层而非服务器层实现的，所以不同存储引擎层支持的索引类型可以不同。例如，虽然 MyISAM 和 InnoDB 的索引都是使用 B+Tree 实现的，但是其实际数据存储结构有不少差异。下图中 B+Tree 示例一共2层，图中每个页面都已经被随机编号（编号可以认定为页面号），其中页面号为 20 的页面是 B+Tree 的根页面（根页面通常是存放在内存中的），根页面存储了 <key+pageno>，pageno 是指向具体叶子节点的页面号。其他页面都是叶子节点，存放了具体的数据 <key+data>。
B+Tree 索引能够快速访问数据，就是因为存储引擎可以不再需要通过全表扫描来获取数据，而是从索引的根结点（通常在内存中）开始进行二分查找，根节点的槽中都存放了指向子节点的指针，存储引擎根据这些指针能够快速遍历数据。例如，通过页面号为 20 的根节点可以快速得知 Key<10 的数据在 pageno 33 的页面，key在 [10,16) 范围的数据在 pageno 56 的页面。
叶子节点存放的 <key+data> ，对于真正要存放哪些数据还得取决于该 B+Tree 是聚簇索引（Clustered Index）还是辅助索引（Secondary Index）。
聚簇索引和辅助索引
聚簇索引是一种数据存储方式，它表示表中的数据按照主键顺序存储，是索引组织表。InnoDB 的聚簇索引就是按照主键顺序构建 B+Tree，B+Tree 的叶子节点就是行记录，数据行和主键值紧凑地存储在一起。 这也意味着 InnoDB 的主键索引就是数据表本身，它按主键顺序存放了整张表的数据。
而 InnoDB 辅助索引（也叫作二级索引）只是根据索引列构建 B+Tree，但在 B+Tree 的每一行都存了主键信息，加速回表操作。
聚簇索引占用的空间就是整个表数据量的大小，而二级索引会比聚簇索引小很多， 通常创建辅助索引就是为了提升查询效率
InnoDB 只能创建一个聚簇索引（假想下如果能支持多个聚簇索引，那就意味着一张表按不同排序规则冗余存储多份全表数据了），但可以创建多个辅助索引。
相比索引组织表，还有一种堆表类型，堆表是根据数据写入的顺序直接存储在磁盘上的。对于堆表而言，其主键和辅助索引唯一的区别就是键值是否唯一，两者都是根据索引列排序构建 B+Tree 的，在每个叶子节点加上指向堆表的行指针（row data pointer） 。堆表在各类数据库中也被广泛使用，MyISAM 存储引擎的表就是堆表。