Mysqls索引实现原理教程

索引的出现为了查找提高查找速度，顺序查找速度过慢，所以索引的存储方式对与查询有很大的影响

1 二叉树

使用二叉树作为数据结构，相对于数组这种顺序结构是快了很多，利用二叉树的特性右子节点比父节点大，左子节点比父节点小的远离进行查找，但是当索引数据出现顺序值，例如1,2,3,4,5,6这样的情况，就会造成二叉树失去了平衡，造成一侧节点大，所以是不合适的

2 红黑树

红黑树相对比二叉树，就是对失去平衡的二叉树做了平衡处理，当一侧节点出现过多的时候，会进行左旋和右旋进行变化保持数的平衡，但是当数据量过大，节点一侧还是会出现失去平衡，查询次数会增多，红黑树这种数据结构还是不适合，数据量小的话还行

3 B-tree和B+tree

B-tree是对红黑树进行了优化，根据红黑树可以看出，如果树的深度太大，就会造成多次查询，多次io，查询很慢，如果树的深度为2或者3 那样岂不是很快，所有B-tree利用这一点，改进了红黑树，增加了节点的内存，每个节点可以横向扩展，挂多个值，没记错的话，子节点可以存储为16K的索引。B-tree的非子节点存储的的是索引值和下一个索引的磁盘地址，一般我们设置树的深度为2~4之间，控制了树的深度，每个节点大概可以存储1176个索引，按照树的深度为3来计算，子节点可以存储大约16K的大小，1176*1176*12=22127616，也就是说可以存储2000万个索引值，最后io查询两次可以定位到数据，一般根节点的索引值是在内存中，这样在内存中进行比对是很快的。mysql存储引擎有个叫做mysam，可以看到文件在磁盘中存储和innodb是不一样，他有三个文件，一个是表的结构，一个是表的数据行，一个就是索引，但是innodb只有两个文件，也即是聚集索引，将索引和数据存储在一个文件中，因为innodb索引的子节点不是数据所在的地址而是数据，这也就是B+tree，相比来说，innodb比mysam少了一次io查询，毕竟mysam是非聚集索引（索引和数据存在两个文件内）