关于数据结构B+TREE 和 HASH的整理

admin2024-05-15  1

一、B+TREE

B+Tree是一种树数据结构,是B-Tree的变种,属于n叉排序树,每个节点通常有多个孩子。

B+Tree是和B-Tree相比,B+Tree的所有的数据都会出现在叶子节点上,并且叶子节点会形成一个单向链表,非叶子节点仅仅起到索引数据作用,具体的数据都是在叶子节点存放的。

在MySQL的索引中,对原本的B+Tree进行了优化,MySQL给每个叶子节点加了一个指针,这个指针会指向它的下一个邻居叶子节点。然后,所有的叶子节点就通过这些指针连成了一个大圈圈,变成一个双向的循环链表。当我们想要查找某个范围内的数据时,可以顺着这个“链表”快速地找到所有相关的数据,这就而不需要再从根节点开始重新查找。而且,如果我们想要对数据进行排序,也可以利用这个“链表”,因为它已经是按照某种顺序排列好的了。

相对Hash索引,B+tree支持范围匹配及排序操作。

二、HASH

HASH采用键值对的方式,哈希(hash)比树(B-Tree)更快,原因就是Hash索引的工作方式其实就像我们生活中的电话本或者地址簿。想象一下,你有一本电话本,里面记录了每个人的联系方式。为了快速找到某个人的联系方式,电话本不是按照人名首字母或者姓氏笔画排序,而是用了一种特别的方法给每个人编了一个号码(这就是哈希值)。

现在,你想找某个朋友的联系方式,你只需要查看电话本前面的索引(哈希函数),找到这个朋友对应的号码(哈希值)。然后,你直接翻到电话本中对应号码的位置,就能迅速找到这个朋友的联系方式(数据)。

所以,Hash索引就是利用一个特殊的编号方法(哈希函数),给每条数据编一个独特的号码(哈希值)。这样,当你需要找某条数据时,只需要用这个号码(哈希值)就能在固定的位置(固定大小的数组)快速找到它,而不需要一页一页地翻找。这种方法非常快捷,但缺点是,如果两个人的号码(哈希值)相同,你就需要再仔细看一下,确保找到的是你要找的那个人(解决哈希冲突)。

对比B+TREE,Hash索引只能用于对等比较(=,in),不支持范围查询(between,>,< ,...),不支持排序操作,在一般情况下查询效率高。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!