锐客网

  1. 首页 > it技术 > >

详解索引底层数据结构 （与B树、B+树、哈希表区别）

Javaweb

以MySQL为准:
1.索引是什么
索引是一种特殊的文件，包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引，并指定索引的类型，各类索引有各自的数据结构实现
2.索引的效果
(1).加快查找的效率
(2).拖慢数据插入,删除和修改的效率
3.索引应用场景
在针对数据库表的某列或某几列创建索引,需考虑以下几点:
(1)数据量较大,且经常对这些列进行条件查询
(2)该数据库表的插入操作,及对这些列的修改操作频率较低
(3)索引会占用额外的磁盘空间
4.索引的数据结构
(1)索引可以考虑的数据结构
二叉树(二叉搜索树) 查找效率(理想)(logN)
哈希表 查找效率:O(1)
但在实际中索引一般都是使用B+树实现底层结构
(2)对比哈希表:哈希表只能处理相等情况,不能处理其他逻辑: > >= …
哈希表查找过程:把key带入哈希函数中,计算得到下标,再根据下标取得对应的链表,再去遍历比较key是否相等
(3)对比二叉搜索树:二叉搜索树每个节点最多有两个叉,当数据较大时,树的高度就比较高,最终操作效率也会下降,还有二叉搜索树直接获取中序遍历也不是很高效O(N)
(4)B树和B+树
详解索引底层数据结构 （与B树、B+树、哈希表区别）
文章图片

B树也二叉树的区别:
i.每个节点不是二叉,而是N叉
ii.每个节点不是存一个数据,而可能是多个数据
B树的相比较二叉搜索树的优势:
i.在B树上查找数据,就是一个N分查找,效率比二分查找快
ii.由于每个节点都存了多个数据,每个节点都有多个度,与二叉树相比较,在保存相同数据的情况下,B树的高度就会比二叉树低很多
详解索引底层数据结构 （与B树、B+树、哈希表区别）
文章图片

B+树与B树相比较:
i.每一层的元素之间都链接到一起
ii.数据只保存在叶子节点上,非叶子节点上只保存一些辅助查找的边界信息
【详解索引底层数据结构 （与B树、B+树、哈希表区别）】B+树的优势:
（1），Ｂ＋树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，ＩＯ操作更少
（2）、其次，因为卫星数据的不同，导致查询过程也不同；Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定
（3）在范围查询方面，B+树的优势更加明显
B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，知道查找到范围的上限即可。整个过程比较耗时。
而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。

    推荐阅读


    上一篇：数据结构与算法|【Java数据结构】哈希表详解

    下一篇：leetcode|集合和数组互转，list，array