索引的概念
索引是一种有序化的数据结构
为什么要有索引
为了提高查询效率
mysql数据库的索引数据结构分析
是二叉树吗？
如果是二叉树，从1-10就会变成单链表，查6要查6次
是红黑树吗
如果是红黑树（平衡二叉树）6要查2次，但是查10要查5次了，如果数据量再多的话，可能就要查N次了，都使用索引了，还要查5次就尴尬了啊
是B树吗
如果用B树（多叉二叉树）就是每个节点可以有多个索引元素，这样就能降低树的高度，比如mysql默认的一个节点就可以存储约16K大小的索引元素，比如是一个bigInt类型的数据8byte作为索引元素，那么每个节点可以存放约16k/8b=1170个索引元素。树基本可以控制再3层1170*1170*1170=反正很大应该有几千万了叭，这样的话就能放下数据库记录了的同时降低树的高度为3，这也就是为什么索引可以使得查询千万级的数据只需要几十毫秒，但是不加索引可能需要几十秒的原因了。但是B树每个节点都存有数据库索引元素对应的data数据，可能是记录对应的磁盘文件地址，也可能是该条记录对应的所有字段，这个和不同的数据库引擎有关，会降低数据容量。所以mysql官方用的是B+Tree
其实是B+树
B+Tree，如下图。原因也有写
因为查询的时候其实是把节点load到内存中，然后再在内存中做查询，显然，内存中查询比数据库在磁盘文件中查询所在行的磁盘文件地址要快很多，所以将非叶子节点都单存储索引元素，数据存储在需要加载到内存中再查询的叶子节点中。内存资源当然也是很宝贵的，所以也不可能将所有数据都加载到内存中来。所以B+树的这种平衡也比较适合索引。叶子节点之间的指针可以加快内存中的访问性能
Hash表的结构
但是B+Tree也不是唯一的一种结构，hash表也是支持的。
HASH索引的结构其实就是用主键索引做一次hash运算，然后将运算得到的散列值作为key，存储再一个hash表中，值对应的就是这个主键对应的磁盘文件地址指针。这样的话，就算是几亿的数据，也可以很快速的定位到。看起来比B+树还要好。需要查询某个主键值的时候直接HASH(主键值)-->去hash表中找。但是这种情况只能处理=的查询，遇到范围查询就JJ了，所以，99的情况是不会用到的...