索引概述
常见索引结构一般分为以下几种
二叉树
红黑树
hash表
B-tree
假设当前生产环境有500W条数据，如果要使用红黑树或者是二叉树，设想索引树的高度要有多高？
可能等于几十。随着数据量的增长，数据量可能增长到1000W，2000w 呢？
索引树查找数据一般是从根节点查找，至少要20次（从根节点）的遍历查找才能准确定位到我们所查找的数据。所以需要20次磁盘IO的操作，性能是可想而知的。红黑树很显然在数据量大的时候也是不理想的。
想要改造，必须要将索引树的高度可控。那么能否有种方法将索引数的高度在几千万量级的数据下，能不能将树的高度控制在h <=4 或h <=3?
是可以的
B树
结构大概如下
B树叶子节点具有相同的深度，叶子节点的指针是空的，它跟B+Tree相比，B+Tree将所有的 数据挪到了最下面的叶子节点。对于树结构来说，影响我们查询效率的，就是我们索引树的高度
B+Tree高度为3的时候能放2200W的数据，，如果具有data数据的页结点，每个元素按照1KB来算，那么B树索引的根节点只能放16个元素，那么如果要放满2200万数据，需要算出16的n次方=2200
那么n就是树的高度，那么B树的高度肯定是远远大于3，这就是为什么在B+tree的时候将根节点上的data元素移动到叶子节点上，就是为了能让根节点存储更多的数据，哪怕一个页节点只有16KB，也可以存更多的
索引元素。索引树的高度说白了，就是由非叶子节点能放多少个索引元素决定的，能放的索引元素越多，索引树的高度就越低，检索的效率就越高。
B+树
它是b树的变种，非叶子节点不存储data,只存储索引（冗余）可以放更多的索引
叶子节点包含所有的索引字段
叶子节点用指针链接，提高区间访问的性能
什么叫冗余索引？说白了就是取你每个叶子节点的第一个元素，这些个第一个元素也就是叶子节点上比较中间的元素
B+树有个特性，每个元素从左到右是有序排列的。15.18.20.30是有序排列的，当然这一点B树也是具备的，这叫—>有序递增
B树和B+树还有个区别，B+树相邻两个叶子节点之间，有指针，也就是说相邻两个叶子节点之间有一小块空间存储着在当前磁盘的位置，在下一个节点的叶子节点的开始也有一小块空间存储当前磁盘空间的位置。根据磁盘的位置就能快速的找到这个元素在磁盘的位置。
B+树查找元素的过程
通其他数据结构一样，B+树查找元素也是从根节点开始查找，会把根节点整个节点的元素都load到内存中去，也就是RAM里面，然后拿我们要查询的元素去内存中做
比对，然后使用折半查找（也叫二分查找）定位到（比如我们需要查询clum=30的元素）30介于15和56之间。然后将15和56之间的数据也load到内存中，最后经过比对将30所在的磁盘的文件地址返回。整个查找的过程大概就是酱紫。
对于mysql来说，像这类的页结点，它的大小大概是16KB，我们可以通过一条sql语句来看到：SHOW GLOBAL STATUS LIKE ‘Innodb_page_size’;
可以看到页节点的大小为16KB，一次磁盘IO与内存计算，这两者之间的性能会差很多很多。其实最耗费时间的，在内存中定位是很快的，特别是使用折半查找。
为啥是16K？
16KB大概能放多少数据？
我们拿bigint来说，bigint占8个字节，中间空白的段是代表一个地址，一个地址在磁盘中大概分配的空间是6个字节，那么16KB大概能放多少个元素？
16KB/8字节+6字节，约等于1170个元素，也就是说，一个页节点，最少可以存放1170个元素，那叶子节点可能特殊一点。因为他有一个data元素
这个data元素有可能比较大，我假设data元素比较大，它放了整条数据，一行数据占用的字节数加起来差不多1KB左右（取决于字段），我假设最后叶子节点上上数据有有16个元素
那么一页数据索引大概能容纳1170117016个元素，2190W 个数据元素，2000多万的数据放到B+Tree里面，其索引树的高度只等于3
那我们要查找某个元素，只要经过3次磁盘IO就可以了，千万级别的表走索引只需要3次即可查到。
B+树还有个指针
MyISAM存储引擎到底是怎么取数据的呢？如下
myISAM索引文件和数据文件是分离的（非聚集）。如上图所示，假设吧cloum1作为查找字段，索引是用B+tree,这张表对应的MYI文件会将数据以左边的
B+tree结构进行组织，在插入每行记录的时候，它会分裂，这张表的记录存在MYD文件，查找的时候会先找MYI（index）文件，从根节点查找，最终遍历到Col1=30所在叶子节点的data元素上，返回对应的磁盘文件地址，根据这个地址去MYD文件中，找到对应数据
而InnoDB对应的文件只有两个，一个是.frm文件，另外一个是.ibd文件。这个ibd文件就是整张数据表的所有数据它也是按照B+tree来组织的 。
都是存储引擎，MyISAM的B+Tree放的是（叶子节点的data元素）磁盘文件的地址
而InnoDB放的是15所在行的其他列的数据。也就是15的索引元素，对应的是所在行的其他列的数据。
也就是这个索引对应了一整行的数据。
所以这里引入一个概念，聚集索引
聚集索引————叶子节点会包含一整行完整的数据记录。我们刚刚演示的为主键索引，其实它就是一个聚集索引
非聚集索引————-MyISAM的主键索引，其实就是一个非聚集索引。
因为它的叶子节点只包含了索引，并没有包含数据。数据则在另外一个文件，也就是MyISAM存储引擎下的.MYD文件。
但是对于InnoDB,索引和数据在同一个文件中，都是在同一个.ibd文件中,可以实现一次性查找。索引文件和数据一旦分离，这样的索引我们称之为——“非聚集索引”。
为什么一定要建表的时候必须要建一个“整形自增”的主键？
很显然，我们刚刚看到mysql开发人员在设计这个表的时候它的IBD文件它必须要用一颗B+Tree来组织，如果我们的表里面有主键，主键自带索引，那么我们就可以主键来组织整张表的数据。
如果这张表没有主键，它会从你这张表的 第一列开始来选择一列所有元素都不相等的一列数据来组织这科B+Tree, 如果所有列的数据都不存在不相等的情况下，那么mysql会帮你建一个隐藏列，这个隐藏列会帮你维护一个唯一的ID，所以建表必须要建主键。
为什么要使用整形自增字段来作为主键呢？
当我们找元素的时候，一版都是从根节点来找，在元素的过程中，一般情况下都是要经过很多次比大小。假设我们现在拿一个字符串UUID作为主键索引，那么设想下，到底是整形比较快，还是一长串UUID比较来的快。字符串比大小它是要逐位去比较，按照ASC码，所以我们推荐使用自增的整形来作为主键。
聚集索引跟非聚集索引单从索引角度来说，聚集索引肯定是要快一些的，非聚集索引需要先从索引文件中拿到磁盘文件的id再去数据文件中查询，效率自然就低，类似于回表操作。
HASH索引
我们来拿这张表举例：选出某一列，比如说Col2 ，我把他设置为哈希索引。当你要查找某个元素的时候，它会将数据存储到hash结构中，HASH结构如下：
在存储索引的时候会对存储的数据做一次哈希运算，比如MD5，CRC16,CRC32都是哈希算法。mysql底层有自己的哈希算法，我如果把这一列数据作为哈希索引，会先把这一列的值求到哈希结果，将结果定位到哈希桶里面去。比如说我再插入爱丽丝Alice这条数据的时候，算出hash值=2，那么就会往后面放一个格子，在插入一条Jim,发现经过运算，jim的哈希散列值也是2，因为哈希会存在哈希碰撞，那么它会将Jim放到哈希桶的2上面，放在Alice的后面去，如果哈希的结果不一样，假如Tom，则会放到其他地方。当我要查一个值的时候，Name这个字段=Alice的时候，当然就是对Alice做一次hash运算，就定位到2上面去，对这个哈希链表做一次遍历，当然哈希链表除了存放索引之外，还把索引元素所对应的的磁盘文件地址放进去只要经过一次哈希运算，就能很快定位到这个元素所在的磁盘地址，这就是哈希结构
Hash不支持范围查找
理想情况下面，有可能经过一次磁盘IO，就能定位到我们所需要的数据，如果B+Tree的话，要很长时间。在某种情况下，哈希有可能比B+树效率还高。
但是在工作中，99.99%的情况下，我们选择的是B+tree，而不是哈希。主要原因在于哈希这种结构，对等值查询，比较好。但是对于范围查询，稍微差点意思。
按照哈希结构，假设我要查找Name这个字段大于Alice,从这个结构没办法去查，因为这里面根本就没有大于这个概念，最终还是需要全表扫描，因为没有用到索引。
为什么B+Tree很好的支持范围查找？
因为在B+Tree中，在叶子节点上，存在一个双向指针，如下图所示：
假设我们需要查找col > 20 这个字段，会先从根节点快速定位到20这个元素上，B+Tree有个索引特点，它是有序的，有序的，有序的！它是从左到右依次排序的，从20开始出发，用指针快速定位到相邻叶子节点的元素，一直将所有大于20 的元素全部拿出来。然而B树没有这个指针，虽然Btree结构也是从左到右依次递增，所以当查到叶子节点，没有办法再去定位，得从根节点重新查找，效率很低。这就是B+树和B树最重要的区别。
若有收获，就点个赞吧
0 人点赞
