mysql数据结构

搜索树（左边子树一定小于右边子树）

优点：可以根据节点有序性快速找到目标节点

缺点：若插入的节点是递增或递减，则会退化为链表，每次搜索都要逐个遍历

平衡树

优点：可以不断平衡树的高度，使树的左右节点的高度不会相差大于1

缺点：若多次插入节点，会导致平衡树不断重构，影响性能

红黑树

优点：可以保证根节点到最远的叶子节点不会大于从根节点到最远的叶子节点的2倍，可以减少树的旋转重构次数，也可以保证左右子树的高度差不会相差太多

缺点：因为红黑树属于二叉树，所以当数据量大的时候，红黑树的高度会变得很高。树的高度越高，搜索进行IO的次数就会越多，会影响到搜索的速度

B-树

优点：由于一个节点上可以放多个多个关键字，因此树的高度会相对的减少，可以减少搜索次数。

缺点：由于数据和索引都放在节点上，当一个节点的空间一定时，由于数据占据了大部分空间，因此存放索引的空间就会大大变少。

B+树

优点：B+树将所有的节点的用来存放索引，把所有的数据都放在叶子节点上。因此在同样的空间下可以存放更多的索引，大大减少了树的高度。因此mysql选择B+树作为索引的数据结构。

索引

回表：非主键索引叶子节点存放的数据不是整行数据，而是存放的主键索引的索引值，因此，需要先拿到主键的值后，再去根据主键索引树中查找。因此，若一个表中有一个主键id和一个字段name。建立了主键id索引和name普通索引。若使用

select * from table where name == '小明'

mysql会进行两次索引搜索。第一次使用name索引搜索拿到id后，使用id再进行一次索引搜索。若使用

select id,name from table where name == '小明'

则只会进行一次索引搜索。因为name索引树中保存了id的值，所以不用进行多一次搜索，这叫做索引覆盖

最左匹配原则

最左匹配原则只会在联合索引中用到

特点：左边的字段是有序的，当只看右边的字段，会发现是无序的。但当左边字段的值一样时，右边的字段是有序的。若把左边的字段看作a，右边的字段看作b

select * from a = 1

该查询语句会用到a的索引

select * from a = 1 and b = 2

该查询语句会使用到a和b的索引

select * from b = 1

该查询语句会放弃使用索引。因为离开字段a，单独看字段b是无序的。因此需要全局搜索