索引
索引是一种用于快速查找磁盘数据的一种数据结构,InnoDB存储引擎的底层用的就是B+Tree数据结构,本篇文章将介绍B+Tree是怎么演变而来的.
索引的优点
在不加索引的情况下,InnoDB存储引擎查询数据会全表扫描.假如一张表有100W数据,那么就需要扫描100w数据.而在加索引的情况下,InnoDB存储引擎内部会根据这个索引列维护一棵B+Tree,查询的时候(where条件存在索引条件)会根据这个索引去查询数据,可以避免全表扫描,减少磁盘的I/O,提高查询效率.
索引的缺点
如果一张表中对数据的操作频繁的插入、更新、删除的话(建立了索引或多个索引),则需要频繁的维护这些B+Tree,给数据库增加一定的维护成本.每一个索引还要占一定的物理空间,所以要合理创建索引.
索引底层可以使用哪些数据结构
- 二叉树
- 平衡二叉树(AVL树)
- R-B Tree(红黑树)
- B-Tree(平衡多路查找树)
- B+Tree(平衡多路查找树,B-Tree的变种)
二叉查找树
二叉查找树需要满足两大特性:
- 每个结点至多有两个孩子结点
- 每个结点大于其左孩子结点小于其右孩子结点(左孩子结点的值小于父结点,右孩子结点的值大于父结点)
依次添加 541,945,88,23,10,5,666 如下图 :
如果我要寻找945这个值,只需要比较两次就可以找到,极端的情况下寻找5,也只是需要比较5次就可以找到.
再来一张,541,510,451,269,61,8 极端的情况下二叉查找树会退化成链表,遍历的时候时间复杂度是O(n) 如下图 :
二叉查找树在极端的情况下会退化为链表,查询时间复杂度为O(n),降低了查找效率,所以为了解决这个问题,平衡二叉树出现了.
平衡二叉树(AVL树)
平衡二叉树在二叉查找树特性的基础上,新增了一个重要的特性: 满足任何结点的两个子树的高度最大差为1(绝对值),也就是说当前结点的两个孩子树的高度差不能超过2,如果没满足这条件的情况下就需要进行平衡操作.
那么如何维持一颗平衡二叉树呢 : 想要维护一颗平衡二叉树,需要做一些额外的操作来维护平衡(四种维护平衡的方式 )
左旋转
左旋转条件:发现结点500的左右孩子高度差不满足最大差为1(3 - 1 = 2),需要通过旋转来维持平衡.(如果根结点500的左孩子的左孩子的孩子是非空结点,则需要进行左旋,也就是说添加结点的时候是添加到根结点的左孩子的左孩子的孩子中的情况下要进行左旋)
右旋转
右旋转条件:发现结点600的左右孩子高度差不满足最大差为1(3 - 1 = 2 ),需要通过旋转来维持平衡.(如果根结点600的右孩子的右孩子的孩子是非空结点,则需要进行右旋,也就是说添加结点的时候是添加到根结点的右孩子的右孩子的孩子中的情况下要进行右旋)
左右旋转
左右旋转条件:发现结点500的左右孩子高度差不满足最大差为1(3 - 1 = 2 ),需要通过旋转维持平衡.(如果根结点500的右孩子的左孩子的孩子是非空结点,则需要进行左右旋,也就是说添加结点的时候是添加到根结点的右孩子的左孩子的孩子中的情况下要进行左右旋)
右左旋转
右左旋转条件:发现结点500的左右孩子高度差不满足最大差为1(3 - 1 = 2 ),需要通过旋转维持平衡.(如果根结点500的左孩子的右孩子的孩子是非空结点,则需要进行右左旋,也就是说添加结点的时候是添加到根结点的左孩子的右孩子的孩子中的情况下要进行右左旋)
AVL树是严格的平衡二叉树,平衡条件必须满足(所有结点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保存平衡,而因为维护一棵AVL树需要多次的旋转,且旋转非常耗时,由此我们可以知道AVL树不适合频繁用于插入与删除的场景,适合于查询遍历多的情况.
基于AVL树的平衡调整旋转次数较多,这样给删除和插入数据的时候带来一定的效率影响,所以红黑树出现了.
红黑树是一种弱平衡二叉树(由于是弱平衡,可以看到,在相同的结点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数少,插入最多两次旋转,删除最多三次旋转,所以对于插入,删除操作较多的情况下,我们就用红黑树.
结论: AVL树适合用于插入与删除次数比较少,但查找多的情况,红黑树则与AVL树相反.
R-B Tree(红黑树)
R-B Tree,全称是Red-Black Tree,又称为"红黑树",它是一种特殊的二叉查找树.红黑树的每个结点上都有表示结点的颜色,要么是红(Red)或黑(Black)
红黑树的特性:
- ①根结点必须是黑色
- ②每个结点要么是红色,要么是黑色
- ③叶子结点指向的是NULL且都是黑色
- ④红色结点的父亲结点和左右孩子结点一定都是黑色(不能连续两个结点是红色)
- ⑤从一个结点到该结点的子孙结点的所有路径上包含相同数目的黑结点(确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树)
红黑树利用左旋和右旋来保证特性④和特性⑤.
而如上图只有10条数据的情况下,树的高度就达到了4层了(树的高度越高,则遍历的效率越低),而在数据为百万数千万级别甚至上亿记录的表创建的树的高度得有多高?可想而知.那既然太高了就会影响查询效率,那只能横向发展了(变胖),所以B-Tree就诞生了.
B-Tree(平衡多路查找树)
B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树.(B树每个结点有多个分支,即多叉、"N"叉树).
一颗m阶的B-Tree的特性 : 这里跟一个最小度数有关 t>=2
- m 代表什么: 一个结点最多只能m个子结点,例如根结点指向子结点最多只有3个子结点(第二层每个结点最多也是只有三个子结点),多于三个结点就会分裂.
- 键值(key):每一层的键值都是从左到右有序递增的(升序),如第一层的74-->484,第2层的:15-->98-->...... ,每一个结点的键值(key)必须大于等于 t-1 ,小于等于2t-1,也就是 t-1<=key<=2t-1
- 指针(指向孩子结点的地址,c):每个结点包含的指针是key+1个,例如第一层:2个key,则第一层结点有3个指针,t<=c<=2t
- 每个结点都会存放data(数据)、key(键值)、c(孩子指针)(每个结点存放data,这样会导致每个结点占用的空间大)
B+Tree(平衡多路查找树,B-Tree的变种)
B-Tree每个结点存放的是键值、孩子指针、数据,这样有一个缺点就是数据较大的时候占用节点的空间也随着增大,存的数据也会减少(不能变得更胖).而B+Tree是怎么解决这一问题的呢(越胖越好) : 非叶子结点只存放指针和键值,叶子结点存放数据,这样的话非叶子结点就可以存更多的键值(可以变得更胖了)
B+Tree的好处:data数据只保存于叶子结点,非叶子结点只存放c(孩子指针)、key(键值),这样非叶子结点(磁盘块、页(page))可以有更多的空间存数据(可以变得更胖了).
结束语
MySQL的InnoDB存储引擎的索引数据结构用的是B+Tree,结点大小(page)设置的默认值是16KB,每一结点都是以页(page)为单位.
一个page里面可以存多个数据,每个page内部的数据是有序的.
B-Tree与B+Tree的主要区别在于把非叶子结点的data元素挪走以后,非叶子结点就能存更多的索引了,那么分叉就更多了.