2、mysql中的索引和树结构

清疚 2022-05-28 06:25 150阅读 0赞

## 二叉树 Binary Search Tree BST ##

二叉树是一种特殊的树结构，普通树若不转化成二叉树，则运算很难实现。  
基本特点：  
    结点的度小于等于2  
    有序树(子树有序，不能颠倒)

满二叉树：一棵深度为k且有2k-1个结点的二叉树。（意思是树上挂满了结点）  
![20160305200812145][]  
完全二叉树：只有最后一层叶子不满，且全部集中在左边:  
![20160305200609019][]

### 顺序存储的优点与缺点 ###

对于完全二叉树来说，顺序存储结构既简单又节约存储空间。  
一般的二叉树采取顺序存储结构时，虽然简单，但容易造成存储空间的浪费。  
在顺序存储的二叉树做插入和删除结点时，要大量移动结点。

对于一般的二叉搜索树（Binary Search Tree），在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。  
所以为了改善查找效率就引入我们接下来要学习的一种更优良的树—-平衡二叉树

## 遍历二叉树 ##

遍历的实质是通过遍历结果将非线性结构的树中结点排成一个线性序列。  
我们得知二叉树有根结点（D）、左子树（L）和右子树（R）三部分组成。

可以得知一共有DLR、LDR、LRD、DRL、RDL、RLD六种方式遍历。但若限定先左后右的原则则只有DLR、LDR、LRD三种情况，分别称为先（根）序遍历、中（根）序遍历、后（根）序遍历。

### 先序遍历 ###

（1）访问根节点；  
（2）先序遍历左子树；  
（3）先序遍历右子数

Status PreOrderTraverse(BiTree T){
     if(T==NULL)return OK;//空二叉树
     else{
         cout<<T->data;//访问根结点
         PreOrderTraverse(T->LeftChild);//递归遍历左子树
         PreOrderTraverse(T->RightChild);//递归遍历右子树
        }
    }

### 中序遍历 ###

（1）中序遍历左子树；  
（2）访问根结点；  
（3）中序遍历右子树。

Status InOrderTraverse(BiTree T){
     if(T==NULL)return OK;//空二叉树
     else{
          InOrderTraverse(T->LeftChild);//递归遍历左子树
          cout<<T->data;//访问根结点
          InOrderTraverse(T->RightChild);//递归遍历右子树
        }
    }

### 后序遍历 ###

（1）后序遍历左子树；  
（2）后序遍历右子树；  
（3）访问根结点。

Status PostOrderTraverse(BiTree T){
    if(T==NULL)return OK;//空二叉树
    else{
        PostOrderTraverse(T->LeftChild);//递归遍历左子树
        PostOrderTraverse(T->RightChild);//递归遍历右子树
        cout<<T->data;//访问根结点
        }
    }

例子：  
![20160308171957482][]  
先序遍历  
\+ \* \* / A B C D E  
中序遍历  
A / B \* C \* D + E  
后序遍历  
A B / C \* D \* E +

## 平衡二叉树 Balanced Binary Tree AVL ##

特点：  
    所有结点的左、右子树深度之差的绝对值≤1。  
![20160313184211798][]  
如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。

LL平衡旋转  
    RR平衡旋转  
    LR平衡旋转  
    RL平衡旋转

## 红黑树 Red-Black Tree RBT ##

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:  
    1）节点是红色或黑色。  
    2）根是黑色。  
    3） 所有叶子都是黑色（叶子是NIL节点）。  
    4） 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)  
    5） 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。  
![SouthEast][]  
参考：[https://blog.csdn.net/sun\_tttt/article/details/65445754][https_blog.csdn.net_sun_tttt_article_details_65445754]  
红黑书vs平衡树性能比较：  
![Center][]  
AA树是Arne Andersson教授在他的论文”Balanced search trees made simple”中介绍的一个红黑树变种，设计的目的是减少RB树考虑的cases。AA树是一颗红黑树，但是规定红色结点不能作为任何结点的左孩子，也就是说红色结点只能作为右孩子。

相关代码下载地址（该内容提供了三中树的Java代码实现）：[https://github.com/bigbird231/Tree][https_github.com_bigbird231_Tree]

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。但是，进行插入操作和删除操作会导致不 再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。 虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次 。

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的reblance，导致效率下降。  
红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

## B树 B-tree ##

上面提及的是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

**B树是一种多叉平衡查找树**，我们之前所介绍的红黑树是二叉查找树结构，B树由于是多叉结构，对于元素数量非常多的情况下，树的深度不会像二叉结构那么大，可以保证查询效率。

面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下， 二叉查找树结构由于树的深度过大而造成磁盘I/O探针读写过于频繁，进而导致查询效率低下，那么如何减少树的深度，一个基本的想法就是：采用多叉树结构。

B树也是一种用于查找的平衡树，但是它不是二叉树。  
![这里写图片描述][70]

特性（m阶/度为m的B树）:

1、树中每个结点最多含有m个孩子（m>=2）；  
2、除根结点和叶子结点外，其它每个结点至少有\[ceil(m / 2)\]个孩子（其中ceil(x)是一个取上限的函数）；  
3、根结点至少有2个孩子（除非B树只包含一个结点：根结点）；  
4、所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(类似红黑树中，Nil,一般没有画出）。  
5、每个非终端结点中包含有n个关键字信息

关键字个数最大4，先取前4个插入到相同的节点中  
![这里写图片描述][70 1]  
插入H，因为步骤一后空间不够，就需要将中间关键字元素上移到父结点中，树增加一层  
![这里写图片描述][70 2]  
继续插入E,K,Q三个节点，继续插就得分裂  
![这里写图片描述][70 3]

## B+树 ##

B树的一种变形树，m阶的B+树和m阶的B树区别：

1、所有叶子节点包含全部关键字信息，及指向含有这些关键字记录的指针，且叶子节点中关键字进行有序链接  
2、非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；  
![这里写图片描述][70 4]

### B+树比B树更适合操作系统的文件索引和数据库索引的原因 ###

1、可以建立更多的索引(b+树的节点只含有关键字的索引，b树包含了关键字的数据信息)  
2、全表扫描更快，因为不用在叶子节点和节点之间切换。

相同点：  
1、叶子节点的关键字都是排序的  
参考：[https://www.jianshu.com/p/db226e0196b4][https_www.jianshu.com_p_db226e0196b4]

## 索引为什么使用B-Tree/B+Tree？ ##

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

为什么不用 红黑树/二叉树？  
因为二叉树的高比b树大。

### MyISAM索引实现 ###

MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址。  
![这里写图片描述][70 5]  
这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：  
![这里写图片描述][70 6]  
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

### InnoDB索引实现 ###

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。  
![这里写图片描述][70 7]  
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶结点包含了完整的数据记录。这种索引叫做**聚集索引**。因为InnoDB的数据文件本身要按主键聚集，**所以InnoDB要求表必须有主键（MyISAM可以没有）**，如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是**InnoDB的辅助索引data域存储相应记录主键的值而不是地址**。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：  
![这里写图片描述][70 8]  
聚集索引这种实现方式使得按主键的搜索十分高效，**但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。**

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

参考：[https://www.cnblogs.com/tgycoder/p/5410057.html][https_www.cnblogs.com_tgycoder_p_5410057.html]

### 联合索引 ###

#### 索引的使用跟查询条件的前后顺序有关吗？ ####

--创建一个表 
    create table testindex ( id int(10) unsigned NOT NULL AUTO_INCREMENT, detail varchar(200) NOT NULL, contact varchar(50) NOT NULL, primary key (id) ) engine=innodb ; 
        )
    --创建索引 
    alter table testindex add index idx(detail, contact);
    --插入一条数据
    insert into testindex(detail, contact) values('aa', 'bb');

按照跟创建index的顺序一致的顺序查询 ；

> explain select \* from testindex where detail =’aa’ and contact =’bb’ ;

发现key:idx,说明使用了索引. 而and语句前后顺序对调：  
![这里写图片描述][70 9]  
key也是idx,说明也使用了索引.

比如建了一个索引idx(A, B, C),他说的是要使用A, AB, ABC这样的顺序查询,而使用B, BC, 这样是使用不到索引的。

#### 为什么不使用第一索引列联合索引失效？ ####

根据b+树的数据结构，联合索引(姓名+年龄)的格式如下:  
(nick\_21)->(nick\_28)->(sunkx\_12)->(mf\_15)…  
所以失去第一个索引查询的话，联合索引是不会被使用的，同理，如果是m个列的联合索引，缺失第一个字段，都不会使用到联合索引。  
如(姓名+城市+年龄)，下面这个查询都不会使用到联合索引：  
where city=’杭州’ and age =19;  
而  
where name=’nick’ and age =19; 是可以使用到索引的。

#### Extra 分析index ####

name上建立了索引。  
select \* from wehre name = ? 与  
select name from wehre name = ?  
在查询上有什么不同？  
经过查看执行计划，发现第二个sql中的extra为 Using index ;

> Using index不读数据文件，只从索引文件获取数据  
> Using where过滤元组和是否读取数据文件或索引文件没有关系

**表明，sql2使用索引就直接返回了，而sql1还要去过滤条件。**其实就是name是索引，直接返回索引。

sql1下是 Using where，Using index；见下面的分析：

Using where：表示优化器需要通过索引回表查询数据；  
Using index：表示直接访问索引就足够获取到所需要的数据，不需要通过索引回表；  
Using index condition：在5.6版本后加入的新特性（Index Condition Pushdown）;  
Using index condition 会先过滤索引条件，过滤完索引后找到所有符合索引条件的数据行，然后才用 WHERE 子句中的其他条件去过滤这些数据行，要回文件索引；

使用 Sakila.rental 表，表中的 customer\_id 建立了名为 idx\_fk\_customer\_id 索引。  
– 第一个 SQL 语句  
EXPLAIN SELECT customer\_id FROM rental WHERE customer\_id = 300;  
这是会使用Using index ；  
– 第二个 SQL 语句  
EXPLAIN SELECT customer\_id FROM rental WHERE customer\_id>=300;  
这是会使用Using index；Using index ；  
优化器会在索引存在的情况下，通过符合 RANGE 范围的条数和总数的比例来选择是使用索引还是进行全表遍历。  
– 第三个 SQL 语句  
EXPLAIN SELECT \* FROM rental WHERE customer\_id =300;  
这是会使用Using index；Using index ；  
因为要获取整行数据，需要回文件索引使用主键获取。

> EXPLAIN SELECT \* FROM rental WHERE customer\_id>=300 AND customer\_id<=350;会使用索引  
> EXPLAIN SELECT \* FROM rental WHERE customer\_id>=300 AND customer\_id<=476;则不会使用索引  
> 索引对 RANGE 值范围有要求。

参考：[https://segmentfault.com/q/1010000004197413][https_segmentfault.com_q_1010000004197413]

### 索引失效的几种情况？ ###

1、如果条件中有or，即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因)  
![这里写图片描述][70 10]  
注意：要想使用or，又想让索引生效，只能将or条件中的列加上索引  
2、对于多列索引，不含有第一列，则不会使用索引(上面已经解释了)  
3、like查询是以%开头  
![这里写图片描述][70 11]  
4、如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引  
![这里写图片描述][70 12]  
5、如果mysql估计使用全表扫描要比使用索引快,则不使用索引

6、查询条件使用函数在索引列上，或者对索引列进行运算  
运算包括(+，-，\*，/，! 等)  
错误的例子：select \* from test where id-1=9;  
正确的例子：select \* from test where id=10;

[20160305200812145]: /images/20220528/9faec0c86b9241b48ee6e182925ce7b1.png
[20160305200609019]: /images/20220528/dbf54b9b83274935ad413b02c4147439.png
[20160308171957482]: /images/20220528/69bcd31448e04fe08c4bc5541ff4a8ec.png
[20160313184211798]: /images/20220528/8696bd8a4dca4653adc14ad27ec7898a.png
[SouthEast]: /images/20220528/f83c601233164b0096c238aadc120120.png
[https_blog.csdn.net_sun_tttt_article_details_65445754]: https://blog.csdn.net/sun_tttt/article/details/65445754
[Center]: /images/20220528/45595bd6e9ab418aaf4015e80992c664.png
[https_github.com_bigbird231_Tree]: https://github.com/bigbird231/Tree
[70]: /images/20220528/0258b52db1fb40daa6cd429733b40e80.png
[70 1]: /images/20220528/8182fcefe2c34d759c404cf78de8f9b8.png
[70 2]: /images/20220528/a425b6f5cfc340eba3715977dfe27987.png
[70 3]: /images/20220528/cecc5e04038c4ea9b6764b1b39c7b894.png
[70 4]: /images/20220528/47affe8ae6f445dbb200f96ce7a8e5da.png
[https_www.jianshu.com_p_db226e0196b4]: https://www.jianshu.com/p/db226e0196b4
[70 5]: /images/20220528/7e02fe186f8049b28a3880d49c15d836.png
[70 6]: /images/20220528/9f721481e723445cba5a284498a3056b.png
[70 7]: /images/20220528/a1a80b6fdee742cbacb25afd16fe070c.png
[70 8]: /images/20220528/1d3525e847e24f18a00b21de68d98ff0.png
[https_www.cnblogs.com_tgycoder_p_5410057.html]: https://www.cnblogs.com/tgycoder/p/5410057.html
[70 9]: /images/20220528/ed7d9792bf804e7ba62723ec6ccf6245.png
[https_segmentfault.com_q_1010000004197413]: https://segmentfault.com/q/1010000004197413
[70 10]: /images/20220528/25c20a4f5dfb4dffa6590e5b0039980d.png
[70 11]: /images/20220528/6de50f882c204895a13ad9dea5feec66.png
[70 12]: /images/20220528/c16c2acfa8dc46d4bfacfa7271bc9107.png