b树索引是什么?有哪些概念?

TheDisguiser 2020-05-27 22:04:49 java常见问答 6771

索引大家都知道吧,你们知道b树索引是什么吗?下面我们要讲解的就是b树索引的应用及原理,快来看看吧。

索引是什么?

索引,是一种概念结构,它一般会用与查询的增强来使用,索引可以在大多数情况下提升查询性能,以MySQL来说,即使没有索引也可以实现应有的功能。

索引是对数据库表中一列和多列的值进行排序的一种结构,使用索引可以快速访问数据表中特定的信息。

通俗的说,索引就是一种结构,在MySQL中,索引和表的存储结构是一样的,都是B树,B树是一种用于查找平衡多叉树,B树的概念如下图:

b树索引

B树,即二叉搜索树,特点:

1.根节点至少有两个子节点

2.所有节点都存储一个关键字,并且以升序排列

3.位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

4.非叶子节点至少有M/2个子节点

看下面结构图:

b树索引

B树的搜索,会从根节点开始,如果查询关键字与结点相同,那么就命中,否则,查询关键字比结点关键字小,就进入左节点,如果比关键字大,就进入右结点;如果左结点或右结点指针为空,则报告找不到相应的关键字。

如果一棵B树的所有非叶子结点的左右子树的节点数目都保持着平衡,那这棵B树的搜索性能就会极其逼近二分查找,但它比连续内存空间的二分查找的优点是:改变B树结构,如插入与删除结点等不需要移动大段的内存数据,甚至通常是常数开销,这也是数据表和索引会采用这种方式存储的优势。

b树索引

B树的特性:

1、整棵树中都分布着关键字集合。

2、出现任何关键字都会且只出现在一个结点中。

3、非叶子结点中搜索有可能会结束。

4、搜索性能等价于在关键字全集内做一次二分查找

5、自动层次控制

因为限制了除结点以外的所有非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率。所以其最低搜索性能为:

b树索引

其中,M为设定非叶子结点最多子树个数,N为关键字总数,所以B-树的性能一般都会等价于二分法查找,也就是没有B树平衡的问题,由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2及诶单,删除结点时,需要将两个不足M/2结点合并,确保平衡。

以上就是关于b树索引的所有内容了,b树结构相对于二叉树稍微复杂不少,想了解更多b树相关的java常见问答知识,就请关注我们吧。

推荐阅读:

b树与b+树的区别是什么?各自有什么优点?

数据库索引是什么意思?特点有哪些?

数据库索引的优缺点是什么?什么情况要建立索引?