Hash结构

1.MySQL5.5版本后默认使用InnoDB存储引擎

74AA5C5AD5FBAA9AAFA8906453008C27.png
InnoDB存储引擎就是用B+树实现其索引结构
索引是数据结构
排好序的快速查找B+树数据结构。
B+树中的B代表（balance）而不是二叉（binary）
在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
B树 多路平衡查找树
IMG_2153(20201031-152502).JPG

区别
1.二叉树会右倾 比如自增队列

image.png
2.平衡二叉树AVL 如果数据量太大，也不行，从瘦高变成矮胖
平衡二叉树又称之为AVL树，之所以多了一个“平衡”二字，是因为和二叉树相比较，左右树高度相差不高于1。
image.png
3.B树 23树 与AVL在于可以减少IO操作，当数据量很大时，整棵树的体量也会很大，每次读取到内存中的树的信息就会很大，消耗资源。
B树与平衡二叉树相似，不同的是B树属于多叉树，又名 平衡多路查找树，数据库索引技术里大量使用是B树和B+树的数据结构，顾名思义，就是每个节点上可以存储多个数值元素。与平衡二叉树不同的是，B树所有的叶子节点都处于同一层级。不存在层级高度差的问题。
IMG_2154(20201031-155313).JPG
image.png
IMG_2156(20201031-155800).JPG
4.B+树
B+树则刚好可以解决这个问题，B树和B+树，本质上都是一样的，只是B+树所有的跟节点和枝节点上只保存关键字索引和其子节点指针，所有的数据信息都被保存到了叶子节点，这样每个枝节点可以存储更多的数据，从而降低树的层级高度，并且所有的叶子节像是一个链表一样，指向右边的叶子节点，从而可以有效加快检索效率，如果需要遍历所有的数据，只需要遍历叶子节点链式结构即可，方便且高效。
image.png
根节点
枝节点
叶子节点
所有的data信息都移动到叶子节点中，而且子节点和子节点之间会有个指针指向，这个也是B+树的核心点，这样可以大大提升范围查询效率，也方便遍历整个树。
1.非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
2.叶子之间，增加了链表，获取所有节点，不再需要中序遍历（左中右）。

IMG_2157(20201031-161726).JPG
IMG_2158(20201031-161950).JPG

区别
非叶子节点只存储键值信息
所有叶子节点之间都有一个链指针
数据记录都存放在叶子节点中