1、mysql 引擎有 InnoDB 和 MyIsAM，本节主讲InnoDB

InnoDB底层：B+tree

MyIsAM底层 ：Hash

2、索引：帮助MySQL高效获取数据的排好序的数据结构

3、建立索引（形容表的，表级别生效）的原因

控制查找次数，提高查找效率

4、InnoDB选用B+tree的原因

 实际上，MySQL查询数据的原理：key（索引字段值，可以看B+Tree那里的叶子节点数据）-value（磁盘地址可以看B+Tree那里的节点data）

常见的数据结构有 二叉树、红黑树、B-Tree、B+Tree等，以这几种为例介绍

归根结底其实选择B+tree是因为树的高度小，这样可以查询效率会高，所以应该选择千万级数据但是树高度比较小的数据结构。高度3-4，数据可存储上千万，答案呼之欲出——B+Tree，以下是验证过程。

可视化数据结构 https://www.cs.usfca.edu/~galles/visualization

1、二叉树

概念特点等 查看百度百科 baike.baidu.com/item/%E4%BA…

特点：右大于左

为什么不用：如果二叉树出现只有右子树或者左子树的情况，那么和链表查询无异，效率低下

2、红黑树-二叉平衡树

树的高度有可能很高很高，虽然自平衡但是树的高度不可控，所以不理想

3、B-Tree-多路搜索树

叶子结点具有相同的深度，叶子节点的指针为空

所有索引元素不重复

节点中的数据索引从左到右递增排序

---横向扩展了节点,缩小了高度

更优解——B+tree

4、B+Tree（B-Tree变种）

拥有B-Tree的优点而且：

非叶子结点不存储data,只存储索引（冗余），可以在同一节点放更多索引，进而缩小树的高度

叶子结点包含所有索引字段

叶子结点使用指针连接（B-tree没有哦），提高区间访问的性能

5、InnoDB B+Tree 存放的数据量与树高度的计算

B+tree一个节点==一页==16kb

bigint在mysql中占8byte，mysql（C语言）一个地址占6byte，

所以 一页索引的数据量==16KB/(8+6)B ==1170个==一个节点放的个数

大多数数据库中一行数据1kb撑死了，所以最后放数据的节点个数==16kb/1kb==16个

如果深度为三，那么 1170*1170*16==21902400, 可以存放两千多万个数据

深度为三意味着如果走B+Tree索引的话，三次磁盘IO就能查到；而走全表查询:需要千万级查询...

有些版本的mysql，将索引节点全部放入了内存，效率进一步提升，所以千万级查找大约只需要把数据从节点取出来的时间。

还有个知识点，对比B-Tree可以明白：树的高度由非叶子节点存放的索引数量决定