SQL-索引
聚类索引
这里需要理解一下为什么使用B+树
数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。
图中第一列表示该行数据在磁盘中的物理地址 ，后面三列才是我们SQL里面用的表里的列，其中id是主键，建立了聚集索引。
结合上面的表格就可以理解这句话了吧 ：数据行的物理顺序与列值的顺序相同，如果我们查询id比较靠后的数据，那么这行数据的地址在磁盘中的物理地址也会比较靠后。而且由于物理排列方式与聚集索引的顺序相同，所以也就只能建立一个聚集索引了。
值得注意的是，最好还是在创建表的时候添加聚集索引，由于聚集索引的物理顺序上的特殊性，因此如果再在上面创建索引的时候会根据索引列的排序移动全部数据行上面的顺序，会非常地耗费时间以及性能。
集索引的好处：索引的叶子节点就是对应的数据节点，可以直接获取到对应的全部列的数据，而非聚集索引在索引没有覆盖到对应的列的时候需要进行二次查询，后面会详细讲。因此在查询方面，聚集索引的速度往往会更占优势。
非聚类索引
该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。
除了聚集索引以外的索引都是非聚集索引，只是人们想细分一下非聚集索引，分成普通索引，唯一索引，全文索引。
- 普通索引：最基本的索引，没有任何限制，是我们大多数情况下使用到的索引。
- 唯一索引：与普通索引类型，不同的是唯一索引的列值必须唯一，但允许为空值。
- 全文索引：全文索引（FULLTEXT）仅可以适用于MyISAM引擎的数据表；作用于CHAR、VARCHAR、TEXT数据类型的列。
- 组合索引：将几个列作为一条索引进行检索，使用最左匹配原则。
索引是通过二叉树的形式进行描述的，我们可以这样区分聚集与非聚集索引的区别：聚集索引的叶节点就是最终的数据节点，而非聚集索引的叶节仍然是索引节点，但它有一个指向最终数据的指针。这句话在下面这篇参考文章中可以好好理解一下。
索引
在数据库系统的使用过程当中，数据的查询是使用最频繁的一种数据操作。算法中有很多优秀的查找算法，但这些算法都只能应用于特定的数据结构上，，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
索引的出现是为了优化数据库的查找性能，但它会对其他数据库操作产生负面影响。
索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。但I/O的消耗远大于内存存取，所以使索引达到更好的效果，需要减少对索引数据的磁盘I/O。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
- 当一个数据被用到时，其附近的数据也通常会马上被使用。
- 程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B+/-树
B-/+Tree检索一次最多需要访问节点：
数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logmN)O(h)=O(logmN)。一般实际应用中，m是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
为什么使用B+树
- 文件很大，不可能全部存储在内存中，故要存储到磁盘上
- 索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数（为什么使用B-/+Tree，还跟磁盘存取原理有关。）
- 局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数，（在许多操作系统中，页得大小通常为4k）
- 数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性
- B+树所有的关键字都出现在叶子节点的链表（稠密索引）中，且链表中的关键字是有序的。非叶子节点只起索引作用（稀疏索引）。叶子节点相当于存储了关键字的数据层。
MySQL学习之——索引(普通索引、唯一索引、全文索引、索引匹配原则、索引命中等)_一个手艺人-CSDN博客_mysql索引