聚簇索引和存储引擎不同的非聚簇索引。数据文件和索引文件的位置不同，但都是在磁盘上而不是在内存上。根据索引文件、数据文件是否放在一起分类：聚簇索引：数据文件和索引文件放在一起，例如：innodb。每个数据库在磁盘上都会有一个对应的文件：进入其中一个文件夹：其中：frm：存放表结构。ibd：存放数据文件和索引文件。注意：mysql的innodb默认会将数据文件和索引文件放在表空间中，不会为每个单独的表保存一个数据文件。如果需要单独保存，必须设置innodb_file_per_table为on。非聚集索引：数据和索引文件分开存储，例如：MyISAMfrm存储表结构。MYI存储索引数据。MYD存储实际数据。索引替代存储结构哈希表。二叉树。B树。B+树。HashMap（哈希表）哈希表可以完成索引的存储。每增加一个索引，都需要计算指定列的哈希值。模运算后计算下标，将元素插入到下标位置。使用场景：等价查询，但是表中的数据是无序数据（范围搜索比较耗时，需要遍历操作），企业中的查询更多的是范围查询，不适合。另外，Hashmap作为索引时，需要加载到内存中，消耗内存。空间。然后考虑树结构。HashMap索引的局限性：哈希索引只包含哈希值和行指针，不存储字段值，因此不能使用索引中的值来避免读取行。哈希索引数据不是按照索引值的顺序存储的，因此不能用于排序。哈希索引也不支持部分索引列匹配查找，因为哈希索引总是使用索引列的全部内容来计算哈希值。哈希索引只支持相等比较查询，包括=、IN()、<>（注意<>和<=>是不同的操作）。它也不支持任何范围查询，例如WHEREprice>100。访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值具有相同的哈希值）。当发生哈希冲突时，存储引擎必须遍历链表中的所有行指针，逐行比较，直到找到所有符合条件的行。如果有很多散列冲突，一些索引维护操作也可能很昂贵。例如，如果在选择性低（很多哈希冲突）的列上创建哈希索引，当从表中删除一行时，存储引擎需要遍历哈希值对应的链表中的每一行，查找并删除对应行的引用，冲突越多，代价越大。树之所以发展，是因为计算机领域的树的特点是左子树小于根节点，右子树大于根节点。它是从左到右排序的，多叉树的查找效率比较低。后来就有了二叉树，接近二叉查找（时间复杂度），但是会出现下面的情况，变成了查询时间复杂度高的链表查询：于是就有了平衡树（AVL树，要求左右节点的高度差不大于1)，即插入数据后，会自旋调整成为平衡树，但旋转会影响插入的性能，即如果有很多查询但是插入很少，可以用AVL树，但是如果插入很多就不合适了。为了优化插入的时间复杂度，生成一棵红黑树，红黑树左右子节点的高度差不大于double（比如左子树的高度为4，则右子树的高度可以为8），但是红黑树的问题是：由于允许子树的高度差超过double，可能会出现磁盘IO读写由于树的深度过大，过于频繁，导致效率低下。为什么会这样？我们知道要获取磁盘上的数据，首先要通过磁盘移动臂移动到数据所在的柱面，然后找到指定的磁盘面，然后旋转磁盘面找到数据所在的磁道，最后读写数据。磁盘IO的开销主要花在搜索需要的柱面，树的深度过大导致磁盘IO读写频繁。根据磁盘搜索访问的次数往往是由树的高度决定的，所以只要我们通过更好的树结构减少树结构来最小化树的高度，B树可以有多个子树，从几十个toupThousands，可以降低树的高度。接下来考虑B树（B-trees）。B树B树的特点是结点（非叶子结点）的子结点个数是可变的（预先设置好），需要在一个结点中设置key值，因为子结点的个数有一个一定的允许范围，所以B树不需要像其他自平衡搜索树那样频繁地重新平衡。B树图：B树的特点：1.所有的键值分布在整棵树中。2.搜索可能结束于非叶子节点，在关键字的完整集合中进行一次搜索，性能接近于二分查找。3、每个节点最多有m棵子树，最多有m-1个键值。4.根节点至少有2个子树。5、一个分支节点至少有m/2个子树（除根节点和叶节点外都是分支节点）。6.所有叶子节点都在同一层，每个节点最多有m-1个key，并且按升序排列。B树键值承载数据示例说明：每个节点占用一个磁盘块，一个节点有两个按升序排列的键和三个指向子树根节点的指针。该指针存储子节点所在磁盘块地址。两个关键字划分的三个作用域对应三个指针指向的子树的数据作用域。以根节点为例，关键字为16和34，P1指针指向的子树数据范围小于16，P2指针指向的子树数据范围为16~34，且P3指针指向的子树的数据范围大于34。关键字查找过程：1.根据根节点找到磁盘块1，读入内存。【第1次磁盘I/O操作】。2.比较区间(16,34)中的关键字28，找到磁盘块1的指针P2。3.根据P2指针找到磁盘块3，读入内存。【第2次磁盘I/O操作】。4、比较区间(25,31)中的关键字28，找到磁盘块3的指针P2。5、根据P2指针找到磁盘块8，读入内存。【第3次磁盘I/O操作】。6、在磁盘块8的key列表中找到key28。缺点：1、每个节点都有一个key，也包含数据，每页的存储空间有限。如果数据比较大，每个节点存储的key数量会减少。2.当存储的数据量很大时，会导致深度很大，会增加查询时磁盘io的数量，进而影响查询性能。B+树特点：B+树与B树类似，只是叶子节点存储数据，其余节点用于索引。B-tree是每一个索引节点都会有一个Data字段。B-tree/B+树的特点是每一层的结点很多，层数很少。目的是减少磁盘IO次数。B树的每个节点都有一个数据字段（指针），这无疑增加了节点的大小。说白了就是增加磁盘IO次数（磁盘IO一次读出的数据量是固定的，单条数据变大，每次读出的次数变少，IO次数增加）增加IO耗时)，而B+树除了叶子节点外不存储数据。节点小，磁盘IO次数少。这是优势之一。另一个优点是：B+树的所有Data字段都在叶子节点中。一般来说，会做一个优化，就是把所有的叶子节点都用指针串起来。这样遍历叶子节点就可以得到所有的数据，这样就可以进行区间访问了。基于范围的查询在数据库中非常频繁，B-树不支持这种遍历操作。说明：B+Tree是在BTree的基础上进行的优化。变化如下：1、B+Tree的每个节点可以包含更多的节点。有两个原因。第一个原因是为了降低树的高度，第二个原因是将数据范围改为多个区间。间隔越多，数据检索越快。2.非叶子节点存储密钥，叶子节点存储密钥和数据。3.叶节点相互指向。Connection（符合磁盘的预读特性），顺序查询性能更高注：B+Tree上有两个头指针，一个指向根节点，一个指向key最小的叶子节点,而所有的叶子节点（即数据节点）都是一个链环结构。因此，可以对B+Tree进行两种查找操作：一种是对主键进行范围查找和分页查找，另一种是从根节点开始的随机查找。1、InnoDB通过B+Tree结构在主键上创建索引，然后将记录存储在叶子节点中。如果没有主键，将选择一个唯一键。如果没有唯一键，则会生成一个6位的row_id作为主键。2.如果创建索引的key是另外一个字段，那么在叶子节点中存放这条记录的主键，然后通过主键索引找到对应的记录，回调回表。
