MYSQL建索引为啥
在Mysql使用中，索引是有很大的作用，极大提升查询效率，索引是一种排好序的数据结构，索引的存在是为了存储到磁盘，高效提供查询的东西。
MySQL索引为啥选了B+树？（二叉树/红黑树/hash表/B树不行么）
考虑数据结构：
二叉树
红黑树
hash表
B-树
假设有表数据为：
第二列加了索引，按照二叉树建索引来看：
此时有条语句查询：
select * from t where col2 =22;
按照col2建索引，实际上找1次就找到了，对于实际mysql查找经历了1次IO，相比较按照顺序查找得找5次，这还是运气好得情况，假如要找34，不建索引还快些1次IO就完了，二叉树索引还得搞2次，来看一种极端情况：
按照col1建索引：
碰到完全有序得节点，跟不建索引没啥区别，甚至查找效率更慢，因为数组是顺序查找，二叉树都是指针链式查找。
再按照红黑树查找来看：
红黑树实际上是二叉树更近一步了，因为经过了高度调整，查找效率提高了不少，找到6，用4次，红黑树在二叉树基础上多了根据节点大小及高度旋转的处理，是特殊的平衡二叉树，具体的可以再研究红黑树。
hash表：
如果按照hash表建索引，性能提升了，根据索引值hash函数处理，再唯一关联记录，是能快速查询了，但是范围查找没办法，hash表的数据结构不支持了。
B-树：
B树在原有红黑树基础上增加了数据节点，不光存索引值：
B树的叶子节点高度相同
B树的叶子节点指针为空
B树的数据索引块节点依次递增
这样解决了hash表不能范围查找的问题，查找到索引对应的数据块，在数据块里二次查找就能查到数据里面的一个范围数，且块里最大数小于右边索引值。
B+树来了：
B+树实际上做了几个调整：
在非叶子节点不存储数据，存储索引，给更多空间放索引。
在叶子节点不存储指针，提供顺序访问指针，提高区间查找性能。
叶子节点里面有冗余一份索引和数据块，这是B+树数据结构提供的特性，方便提供关键字查找和范围查找。
总结下：
到这里基本上能大致上看到为啥是B+树作为索引的数据结构了，而且大概计算下，内存一次性只能存放16KB大小数据，而索引节点bigint类型8Byte大小，指针节点6byte，数据块有索引个数为16KB/14byte=1170个，而到第二层一样的，第三层叶子节点是1kb，data数据最大为1KB，数据是默认一页一页读取的，mysql里面show gloabal status like "innodb_page_size";能查到是16KB大小的块，这样能存1170117016 大概是2千万行的数据大小，这样mysql就是一棵树解决千万条数据查找咯。实际上到了千万也不能放单表了，要分库分表了，不然太影响其它更新性能。
MySQL索引不同存储引擎一样么？
上面总结没考虑到mysql存储引擎的情况，innodb默认叶子节点是直接存储数据行的，而myisam不是，它的叶子节点是只存指针值，它的数据文件和索引文件是分开的在磁盘上，又称为非聚集索引，innodb由于数据和索引文件一块的，是聚集索引。innodb和myisam都是表级的引擎，也就是建表指定的，innodb在数据库上是idb文件和frm（存储表结构的），而myisam是frm和myd,myi文件，myi是存储索引的，myd是存放数据行的。
二叉树的结构不适合那种排好序的字段索引，红黑树当数据量超级大时候，二叉树的高度会增长很多，当查询节点刚好是叶子节点，查询效率很低，hash表的话，不支持范围查找，范围查找使用不了索引，而范围查找使用场景还比较多，为了解决这个问题，衍生了B+树的结构作为索引。
innodb索引相比较myisam查询更高效，innodb的存储有些要求：
1.innodb表本身就是按B+树的组织的索引结构文件。
innodb表必须要有主键，而且必须主键是整形递增的（没有指定的情况下，mysql自己建一个主键，不会报错）。因为整形相比较UUID的容易比较，整形数比较更快，而且整形数占空间更小，int与varchar在mysql里面比较下，为什么是递增的，在插入新数据时候建索引更方便，因为叶子节点里面数据也是顺序放的，递增只需要往后加，而非递增的可能就破坏了叶子节点数据的大小，毕竟最大16K，造成B+树分裂，要重新排列叶子节点了。
innodb非主键索引叶子节点存储了主键值。存储了主键值为了跟主键索引保持一致，同时也是节省空间，有了主键索引，不需要再二次新建。
叶子节点包含完整的数据行。
