b树索引原理是什么?

TheDisguiser 2020-07-13 16:52:24 java常见问答 7306

b树小伙伴们有了解过吗?在文件系统中b树经常用于查询,这次我们就来了解下b树的索引原理吧。

什么是索引?

以SQL Server来说,索引是一种增强式的存在,这意味着,即便没有索引,SQL Server仍然能够实现应有功能。但实际上索引可以在大多数情况下大大提升查询性能高。在OLAP中尤其明显,如果想要完全理解索引的概念,就需要了解大量原理性的知识,如B树,堆,数据库页,区,填充因子,碎片,文件组等一系列相关知识。

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

索引是一种结构,在SQL Server中,索引和表(这里值得是加了聚集索引的表)的存储结构是一样的,都是B树,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树索引的所有内容,更多相关java架构师常见问题请关注奇Q工具网了解详情吧。

推荐阅读:

b树是二叉树吗?b树是什么树?

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

b树是如何建立的?b树基础原理详解