您的位置:首页 > 健康 > 美食 > 网站空间域名续费_简单大气网页_2021年搜索引擎排名_免费创建网站的平台

网站空间域名续费_简单大气网页_2021年搜索引擎排名_免费创建网站的平台

2025/3/14 11:24:10 来源:https://blog.csdn.net/GzlAndy/article/details/146120732  浏览:    关键词:网站空间域名续费_简单大气网页_2021年搜索引擎排名_免费创建网站的平台
网站空间域名续费_简单大气网页_2021年搜索引擎排名_免费创建网站的平台

目录

1 索引常用的数据结构

1.1 二叉树

1.2 平衡二叉树

1.3 红黑树

1.3 Hash表

1.4 B树

1.4 B+树

2 MySQL索引的数据结构

2.1 MyISAM存储引擎索引

2.2 InnoDB存储引擎索引

2.2.1 聚集索引

2.2.2 非聚集索引

2.2.3 联合索引数

2.2.4 hash索引


1 索引常用的数据结构
1.1 二叉树

二叉树特点:

  • 最顶端的称为根节点
  • 没有子节点的称为叶节点
  • 节点中k-v数据结构,key必须,v非必须
  • 非叶子节点只能允许最多两个子节点存在
  • 每个节点比左子树所有节点的值大,比右子树所有节点的值小

二叉树查找:

  • 采取二分查找
  • 最大查找的次数为树的高度
  • 查找的时间复杂度为O(log n)

那么如果key的数据分布特点是单调递增或者递减呢?

  • 二叉树会退化为链表
  • 查找的时间复杂度变为O(n)
1.2 平衡二叉树

为解决二叉树存在的问题,引入了平衡二叉树

当左子树高度和右子树高度的差大于1时,进行旋转,那么就得到了平衡二叉树

平衡二叉树特点:

  • 每个节点最多有两个子节点
  • 每个节点的值比左子树所有节点的值大,比右子树所有节点的值小
  • 每个节点的左子树的高度与右子树的高度差不超过1

那么为了保证二叉树的平衡,在插入数据需要进行一定的操作来保持二叉树的平衡,包括以下几种情况:

左左右

  • 插入1节点后导致3号子树与8号子树高度差大于1
  • 产生的原因是3号节点的子树节点多了一个节点,此时将3号节点

  • 右旋的流程为(当前节点为3节点,右旋就是让自己变成右子节点)
    • 将父节点的左子节点设置为左子节点
    • 将左子节点的右子节点设置为当前节点

左右左右

  • 插入4节点后导致5子树与8子树高度差大于1
  • 产生的原因是5节点的子树多了一个节点,此时先将3节点旋,再将5节点

  • 左旋流程(当前节点为3节点)
    • 将父节点的左子节点设置为右子节点
    • 将右子节点的左子节点设置为当前节点
  • 右旋流程(当前节点为5节点)
    • 将父节点的左子节点设置为左子节点
    • 将左子节点的右子节点设置为当前节点

右右左

  • 插入5节点后导致3子树与8子树高度差大于1
  • 产生的原因是3节点的子节点多了一个节点,此时将3节点旋解决问题

  • 左旋流程(当前节点为3节点)
    • 将父节点的左子节点设置为右子节点
    • 将右子节点的左子节点设置为当前节点

右左右左

  • 插入4节点时导致3子树与8子树的高度差大于1
  • 产生的原因是3节点的右子节点多了一个左子节点,此时将5节点右旋后再将3节点左旋解决

  • 右旋流程(当前节点为5节点)
    • 将父节点的右子节点设置为左子节点
    • 将左子节点的右子节点设置为当前节点
  • 左旋流程(当前节点为3号节点)
    • 将父节点的左子节点设置为右子节点
    • 将右子节点的左子节点设置为当前节点

思考:以上四种情况均考虑的是左子树高度大于右子树高度,那么反过来时又该如何呢?

平衡树虽然解决了数据单调递增或者递减时导致退化为链表的问题,但是在插入时,需要频繁的旋转来保持二叉树的平衡,对于插入修改的性能影响极大。

1.3 红黑树

为解决平衡二叉树插入更新时频发旋转带来的性能问题,引入了红黑树,红黑树通过以下两方面避免了频繁旋转问题

  • 红黑树在某些时候允许左右子树的高度差大于1,只要符合红黑树规则即可
  • 红黑树不平衡时,不一定非要旋转才能平衡,也可以通过改变颜色达到平衡

红黑树特点:

  • 规则1每个节点不是黑色就红色
  • 规则2根节点是黑色
  • 规则3红色节点的子节点都为黑色
  • 规则4所有所有叶子节点都是黑色
  • 规则5每个节点到叶子节点的每个路径黑色节点的个数都相等

红黑树变色逻辑

  • 新插入的节点总认为是红色
  • 如果在插入之后不符合规则,则变色

  • 变色逻辑(当前节点为2节点)
    • 父节点和叔节点变黑
    • 如果祖父节点不是根节点,则变为红色,然后递归检查是否需要变色
    • 如果是祖父节点是根节点,则不变,完成变色

红黑树旋转逻辑

  • 变色之后如果还不满足红黑树规则进行选择
  • 旋转规则平衡一致

红黑似乎已经解决很多问题那么再来想一下数据量很大时候会导致红黑高度增大那么检索时候最差情况下每个节点产生一次磁盘IO对于检索性能影响巨大

1.3 Hash表

  • hash大多情况下只需要计算一次hash就可以定位元素位置
  • hash冲突问题严重hash也会退链表导致检索性能降低
  • 仅仅只能满足=in查询不支持范围查询

1.4 B树

B-Tree特点

  • 节点索引从左递增序列
  • 所有的索引元素不重复
  • 叶子节点叶子节点包含数据
  • 叶子节点具备相同深度并且节点指针为空

B一个节点包含多个数据可以有效降低高度从而加快检索性能

但是因为非叶子节点包含数据会导致以下问题

  • 一个叶子节点包含数据有限
  • 插入如果一个节点数据达到上限势必导致数据分裂合并
  • 而且由于非叶子节点包含数据数据页分裂合并将会发生非常频繁
  • 如果需要进行范围查询如何实现高效查询

1.4 B+树

B+Tree特点

  • 叶子节点不存储data存储索引使得可以容纳数据量
  • 叶子节点包含所有索引数据
  • 叶子节点按照索引递增排序并且两个相邻叶子节点双向指针

B+由于非叶子节点仅仅包含索引使其相同数据情况下高度远远低于B从而加快检索效率

2 MySQL索引的数据结构
2.1 MyISAM存储引擎索引
  • MySQLMyISAM存储引擎数据文件索引文件分离

  • MyISAM存储引擎索引数据结构

  • 采用B+数据结构进行一些调整
  • MyISAM叶子节点不存储真正数据而是存储数据指针
  • MyISAM索引属于非聚集索引
2.2 InnoDB存储引擎索引
  • MySQL InnoDB数据文件和索引文件同一个

2.2.1 聚集索引
  • InnoDB聚集索引一个标准B+
  • 叶子节点存储真实记录
  • 记录会将数据存储别的数据然后叶子节点存储部分数据以及指向其余数据指针

  • InnoDB肯定会有一个充当聚集索引
  • 创建指定主键主键聚集索引
  • 指定主键选定唯一索引聚集索引
  • 没有唯一索引innodb生成rowid充当聚集索引

2.2.2 非聚集索引

除了聚集索引InnoDB还可以创建辅助索引提升查询效率

辅助索引又称为非聚集索引

InnoDB辅助索引采用B+数据结构,但其叶节点存储的是主键值,而非真实数据

  • 拿到主键通过回表方式在聚集索引检索匹配数据
2.2.3 联合索引数
  • 联合索引给多个字段创建索引
  • 排序规则依次按照字段顺序进行排序
  • 上一个字段相同按照下一个字段进行排序

  • 按照联合索引排序规则得出,查询查询条件需要严格按照联合索引字段顺序给出查询条件中缺某个索引字段字段不能通过索引查询
  • 以上最左前缀匹配原则

2.2.4 hash索引
  • hash索引数据结构一致但是存储主键
  • 然后拿到主键进行回表查询

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com