数据库索引理解,基于索引的二叉树,B树,B+树理解。
数据库索引理解,基于索引的二叉树,B树,B+树理解。
理解索引从以下几个问题开始:
1.为什么使用索引?- 快速查询数据
通常查询数据,需要将全表扫描加载进入内存,耗时费力。为了避免全表扫描,采用类似字典方式增加索引,以提高查询效率。
2.什么信息可以做索引?-主键,唯一键,普通键等。(后续详细说明)
3.索引的数据结构?
1.建立二叉树结构(复杂的有红黑树,平衡二叉树,线性二叉树)进行查找。
2.建立B -Tree结构进行查找。
3.建立B+ -Tree结构进行查找。
4.建立hash结构进行查找。
二.二叉树:平衡二叉树(时间复杂度Olog(n)),要求左右节点的高度相差不超过1.
线性二叉树(时间复杂度O(n))
缺陷:二叉树是为了提高查询速度,但是有限于二叉树的每个根节点下最多存在两个子节点,所以大量数据的存储会造成二叉树的深度急剧增加,在查询时,会增加大量的I/O,影响效率。(查询开始,首先进入根节点加载进内存,在判断查询目标位于根节点的左右两边加载内存,再依次循环)
三.B -Tree
B树定义:1.根节点至少包括两个子节点。
2.树中每个节点最多有m个孩子(m阶B-Tree)
3.除根节点和叶节点外,其它每个节点至少有ceil(m/2)个子节点,ceil函数取上限。
4.所有叶节点都处于同一高度同一层。
关键字必须按顺序排列,关键字的左子节点必须<上层最左边关键字,关键字的中间子节点必须<>上层左右关键字,右节点同理,注意全部是开区间。
这些约束是为了减少树的深度,减少I/O1
四.B+ -Tree
相比B树,关键字按顺序排列,关键字左节点<=上层左侧关键字 ,中间>=左侧 <右侧 (前开后闭),右侧>=
相比B+树更适合作于存储系统:
****1.B+树的磁盘读写代价更低。B+树内部节点(除叶子节点)并没有指向关键字具体信息的指针,也就是说不存储具体的数据,只存放索引信息,因此其内部结构与相比较B树更小,所容纳的关键字也就更多,一次性读入内存的所需查找关键字数量也就越多,相对来说。I/O次数更少,查询速率更高。
内部节点并不是最终指向文件内容的节点,而是指向叶子节点关键字的索引。
2.B+的查询效率更稳定。(Olog(n))因为关键字存储在叶子节点,每次查询数据都需要从根节点到叶子节点为止,所以每一个数据的查询效率都基本稳定。
3.B+更有利于对数据库的扫描。B树没有解决元素遍历效率低下的问题。
B+只需要遍历叶子节点,就可以遍历对所有关键字的扫描。**因为每个叶子节点都是用指针做链接的。能够做范围查询。**参照图二的最下方。