AVL 树和红黑树这些二叉树结构的数据结构可以达到最高的查询效率这是毋庸置疑的。

既然如此，那么数据库索引为什么不用 AVL 树或者红黑树呢？

这就牵扯到一个问题了，不考虑每种数据结构的前提条件而选择数据结构都是在耍流氓。

AVL 数和红黑树基本都是存储在内存中才会使用的数据结构，那磁盘中会有什么不同呢？

这就要牵扯到索引的存储原理了

页是 InnoDB存储引擎管理数据库的最小磁盘单位。

一个页中包括很多数据行。

那么，现在问题就来了

一个父节点只有 2 个子节点，并不能填满一个页上的所有内容啊？那多余的内容岂不是要浪费了？我们怎么才能把浪费的这部分内容利用起来呢？哈哈，答案就是 B+ 树，让一个父节点有多个子节点就可以了。

由于 B+ 树分支比二叉树更多，所以相同数量的内容，B+ 树的深度更浅，深度代表什么？代表**磁盘 io 次数**啊！

所以，涉及到磁盘上查询的数据结构，一般都用 B+ 树啦。

B+Tree的性质：

M阶的B+Tree:叉树

（1）每个节点最多有m个子节点
（2）除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整，比如5/2=3。 3/2=ceil(1.5)=2
（3）根节点要么是空，要么是独根，否则至少有2个子节点
（4）有k个子节点的节点必有k个关键码:就是 有m个数据就有m个叉叉；
（5）叶节点的高度一致：这个的 好处是什么？ 当然是稳定啦，查询稳定，想想mysql的索引

B+Tree数据结构：

B+Tree在Mysql中的分析

1.阶数：通过上面的分析我们知道这个阶数很重要直接决定了B+Tree的查找效率以及性能，那么在Mysql中我们如何设定这阶数呢？

通过mysql的页大小决定，一般是16k。那么一个主键类型为bigint的字段建索引大约的消耗空间是多少呢？

Int：8字节，指针一个也算4字节。

一页的节点：16kb/ (8b+8b)=1k 键值+指针
我们刚举例的3阶B+Tree你们计算下可以存多少索引值？

102410241024=1073741824 大约10亿

可想而知如果在理想情况下 我们的mysql查询是不是很高效，一般最多也就4阶左右的B+Tree

根据我们所学的数据结构知识，我们应该如何正确的建立索引：

1.索引不能太多，因为B+tree的插入和删除是要维护的，太多的索引会导致插入变慢。

2.建了索引的字段不能使用like ‘%%’否则是失效的

3.建索引的字段类型不能太大，字段越小阶数就越大，效率就越高，int 和 bigint，varchar（10），varchar（100），text，lontext；B+Tree。全文索引

4.建索引的字段值不能太多一样的，数学里面有个叫什么散列多一些（离散），比如我们把性别建索引会出现啥情况？左边都是一样的值 过滤不了一半。User sex单独建索引 0 1

5.联合索引的最左匹配原则。Select * from user where name = ‘赵云’ and id = 1 我的对（ id,name)建的索引，mysql解析的时候会自动优化。

Select * from user where name = ‘赵云’ and age=10我的对（ id,name,age)建的索引

6.NOT IN 是不会走索引的 not in (1,2,3)
In的值太多 mysql会报错的。上线的

MySQL索引为什么用B+树不用B树

1. B树所有节点都会存储数据，所以查询结果并不稳定，而B+树数据都存放在叶子节点，查询效率更稳定
2. B树只适合随机检索，B+树支持随机检索和顺序检索，B树叶子节点是没有链表的
3. 一般来说索引本身也很大，往往以索引文件的形式存储在磁盘上，这样索引查找过程就要产生磁盘IO消耗。B+树的内部节点只作为索引使用，其内部节点（非叶子节点）比B树更小，判断能容纳的节点中关键字更多，一次读取到的键更多。
4. B树在一定程度上也提高了磁盘IO性能，但没有解决遍历效率低下的问题。B+树的叶子节点都使用指针顺序连接在一起，只要遍历叶子节点就可以实现所有值。
5. 增删文件时，B树需要重新调整树结构。B+树不需要调整树结构，因此B+树效率更高。

根据我们所知道的数据结构知识，我们应该如何正确的建立索引：

1.索引不能太多，因为B+tree的插入和删除是要维护的，太多的索引会导致插入变慢。
2.建了索引的字段不能使用like ‘%%’否则是失效的
3.建索引的字段类型不能太大，字段越小阶数就越大，效率就越高，int 和 bigint，varchar（10），varchar（100），text，lontext；B+Tree。全文索引
4.建索引的字段值不能太多一样的，数学里面有个叫什么散列多一些（离散），比如我们把性别建索引会出现啥情况？左边都是一样的值 过滤不了一半。User sex单独建索引 0 1
5.联合索引的最左匹配原则。Select * from user where name = ‘赵云’ and id = 1 我的对（ id,name)建的索引，mysql解析的时候会自动优化。
Select * from user where name = ‘赵云’ and age=10我的对（ id,name,age)建的索引
6.NOT IN 是不会走索引的 not in (1,2,3)
In的值太多 mysql会报错的。上线的
7、尽量使用覆盖索引，减少回表操作，提高查询效率
8、InnoDB种通常我们自己创建的索引叫辅助索引(非聚集索引)：叶子节点存储的主键索引地址的值，真正取数据会再回表根据主键索引取到真正的数据，也就是说会有两棵树，需要找两次
9、主键索引：在mysql中使用数据库引擎是InnoDB时主键索引就是聚集索引

对于Innodb，主键毫无疑问是一个聚集索引。但是当一个表没有主键，或者没有一个索引，Innodb会如何处理呢。请看如下规则：
1、如果一个主键被定义了，那么这个主键就是作为聚集索引
2、如果没有主键被定义，那么该表的第一个唯一非空索引被作为聚集索引
3、 如果没有主键也没有合适的唯一索引，那么innodb内部会生成一个隐藏的主键作为聚集索引，这个隐藏的主键是一个6个字节的列，改列的值会随着数据的插入自增。
4、自增主键会把数据自动向后插入，避免了插入过程中的聚集索引排序问题。聚集索引的排序，必然会带来大范围的数据的物理移动，这里面带来的磁盘IO性能损耗是非常大的。 而如果聚集索引上的值可以改动的话，那么也会触发物理磁盘上的移动，于是就可能出现page分裂，表碎片横生。所以不应该修改聚集索引。

二叉查找树，红黑树，B-Tree，B+Tree 的区别：
1、二叉查找树：二叉搜索树，优点查找快，但是在某些情况下会退化成链表，它是所有
高效查找树的基础，如果不懂这个 其他的也学不懂。根本性的东西，最好能自己手写出来。
2、红黑树：内存查找高效树，不适合大数据量 也不适合磁盘存储的。具体的分析就是IO浪费以及读取资源浪费，还有就是树的深度会很大。适合一些底层系统做内存运算
3、B-Tree:可以认为是B+Tree过度。只需要知道BTree就可以
4、B+Tree：最适合大数据的磁盘索引，经典的MySql，所有的数据都存在叶子节点。其他都是索引，增加了系统的稳定性以及遍历以及查找效率
不同：关键字和Key值。数据存储的地方，双向链表。
M阶：这个由磁盘的页面大小决定，磁盘快和页内存都是4KB。我们的节点数也就是我们的M值 应该要尽可能的跟他一样。1 0.75的原则HashMap。这样的好处就是为了我们一次刚好能全部拿出一个节点里面存的所有的数据。