MySQL索引的底层数据结构原理剖析(二叉树、 红黑树、Hash、B-Tree、B+Tree)
最新回答
给我来半斤帅哥
2020-10-26 15:30:49
学习各种数据结构图解网站：cs.usfca.edu/~galles/visualization/Algorithms.html(推荐)
下图，左边表格是没有索引，右边是二叉树索引，以col2为索引列。下图说明了有索引和没索引的区别。
分析下面SQL语句：select * from t where col2 =89；
(1). 左边没有索引，搜索col2=89需要从上往下搜索，6次 才能找到，也就是 6次回表操作（6次IO）。
(2). 右边是二叉树索引，搜索col2=89搜索2次 就可以找到，也就是 2次回表操作（2次IO），性能提升明显。
(1). 二叉树的特点：左子节点值 < 节点值；右子节点值 > 节点值；当数据量非常大时，要查找的数据又非常靠后，和没有索引相比，那么二叉树结构的查询优势将非常明显。
(2). 二叉树出现单边增长时，二叉树变成了“链”，这样查找一个数的时候，速度并没有得到很大的优化。
(1). 红黑树的特点：节点是红色或者黑色；根节点是黑色；每个叶子的节点都是黑色的空节点（NULL）；每个红色节点的两个子节点都是黑色的；从任意节点到其每个叶子的所有路径都包含相同的黑色节点。
(2). 存在的问题：红黑树虽然和二叉树相比，一定程度上缓解了单边过长的问题，但是它依旧存储高度问题。假设现在数据量有100万，那么红黑树的高度大概为 100,0000 = 2^n， n大概为 20。那么，至少要20次的磁盘IO，这样，性能将很受影响。如果数据量更大，IO次数更多，性能损耗更大。所以红黑树依旧不是最佳方案。
上述红黑树默认一个节点就存了一个 (索引+磁盘地址)，我们设想一个节点存多个 （索引+磁盘地址），这样就可以降低红黑树的高度了。实际上我们设想的这种结构就是 B-Tree。
(1). Hash索引原理：事先将索引通过 hash算法后得到的hash值(即磁盘文件指针）存到hash表中。在进行查询时，将索引通过hash算法，得到hash值，与hash表中的hash值比对。通过磁盘文件指针，只要一次磁盘IO就能找到要的值。例如，要查找col=6的值。hash(6) 得到值，比对hash表，就能得到89。性能非常高。
(2). 存在的问题：hash表索引存在问题，如果要查询 带范围的条件时，hash索引就无法高效查询。
(1). B-Tree索引特点：B-Tree是一种平衡的多路查找（又称排序）树，在文件系统中和数据库系统有所应用，主要用作文件的索引，其中的B就表示平衡（Balance）。为了描述B-Tree，首先定义一条数据记录为一个二元组 [key, data]，key为记录的键值key，对于不同数据记录，key是互不相同的；data为数据记录除以key外的数据 （这里指的是聚集索引）。那么B-Tree是满足下列条件的数据结构：d 为大于1的一个正整数，称为BTree的度；h为一个正整数，称为BTree的高度；key和指针互相间隔，节点两端是指针；叶子节点具有相同的深度，叶子节点的指针为空，节点中数据索引从左往右递增排列。
(2). B+Tree索引特点：B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
(1). 聚集索引也叫主键索引，叶子节点中的data存储的是该主键对应整行数据。
(2). 非聚集索引也叫辅助索引，叶子节点中的data存储的该索引对应的该行数据的主键值。非聚集索引的寻址过程分两种情况：如果非聚集索引已经索引覆盖了，那么只需要遍历这非聚集索引这一个B+Tree即可，如果不能索引覆盖，那么先需要在非聚集索引这个B+Tree上两次IO找到该行数据对应的主键值，然后拿着主键去聚集索引的B+Tree上找对应的其它数据。
(1). 为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
① 后面的主键索引总是大于前面的主键索引，在做范围查询时，非常方便找到需要的数据。
② 在添加的过程中，因为是自增的，每次添加都是在后面插入，树分裂的机会小；而UUID大小不确定，分裂机会大，需要重新平衡树结构，性能损耗大。
(2). 为什么非主键索引结构叶子节点存储的是主键值，而不是全部数据？
① 节省空间：指向主键的节点，不用再存储一份相同的数据；（否则的话，如果建立多个非主键索引，每个上面都存储的完整数据，非常占用空间）
② 数据一致性：如果修改索引15 的数据，那只要修改主键的 data，而如果非主键的data也存一份的话，那得修改两份，这样就涉及到事务一致性的问题，耗时，性能低。
(3). 为什么希望使用覆盖索引？如果非聚集索引中能索引覆盖，那么我们只需要遍历非聚集索引这个B+Tree从其中的Key里拿到索引值就可，只需要遍历一棵树。如果不能索引覆盖，需要先遍历非聚集索引，然后拿到data中存储的主键值，再去聚集索引中遍历查找数据，相比索引覆盖的话，IO次数更多，性能相对低。
MyISAM和InnoDB的索引结构对比：MyISAM下索引结构文件是分开的，存储引擎在磁盘中文件有三个，分别是数据表定义文件、索引文件、数据文件。InnoDB存储引擎它的表数据文件本身就是按 B+Tree 组织的一个索引文件。一个frm文件存储数据表定义，一个ibd文件存放的索引和实际数据。InnoDB在查找数据时，性能比MyISAM高。
热门标签
