侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

简单谈谈Mysql索引与redis跳表

Redis  /  管理员 发布于 7年前   293

摘要

面试时,交流有关mysql索引问题时,发现有些人能够涛涛不绝的说出B+树和B树,平衡二叉树的区别,却说不出B+树和hash索引的区别。这种一看就知道是死记硬背,没有理解索引的本质。本文旨在剖析这背后的原理,欢迎留言探讨

问题

如果对以下问题感到困惑或一知半解,请继续看下去,相信本文一定会对你有帮助

  • mysql 索引如何实现
  • mysql 索引结构B+树与hash有何区别。分别适用于什么场景
  • 数据库的索引还能有其他实现吗
  • redis跳表是如何实现的
  • 跳表和B+树,LSM树有和区别呢

解析

首先为什么要把mysql索引和redis跳表放在一起讨论呢,因为他们解决的都是同一种问题,用于解决数据集合的查找问题,即根据指定的key,快速查到它所在的位置(或者对应的value)

当你站在这个角度去思考问题时,还会不知道B+树索引和hash索引的区别吗

数据集合的查找问题

现在我们将问题领域边界划分清楚了,就是为了解决数据集合的查找问题。这一块需要考虑哪些问题呢

  1. 需要支持哪些查找方式,单key/多key/范围查找,
  2. 插入/删除效率
  3. 查找效率(即时间复杂度)
  4. 存储大小(空间复杂度)

我们看下几种常用的查找结构

hash

hash是key,value形式,通过一个散列函数,能够根据key快速找到value

B+树

B+树是在平衡二叉树基础上演变过来,为什么我们在算法课上没学到B+树和跳表这种结构呢。因为他们都是从工程实践中得到,在理论的基础上进行了妥协。

B+树首先是有序结构,为了不至于树的高度太高,影响查找效率,在叶子节点上存储的不是单个数据,而是一页数据,提高了查找效率,而为了更好的支持范围查询,B+树在叶子节点冗余了非叶子节点数据,为了支持翻页,叶子节点之间通过指针连接。

跳表

跳表是在链表的基础上进行扩展的,为的是实现redis的sorted set数据结构。 level0: 是存储原始数据的,是一个有序链表,每个节点都在链上 level0+: 通过指针串联起节点,是原始数据的一个子集,level等级越高,串联的数据越少,这样可以显著提高查找效率,

总结

数据结构 实现原理 key查询方式 查找效率 存储大小 插入、删除效率
Hash 哈希表 支持单key 接近O(1) 小,除了数据没有额外的存储 O(1)
B+树 平衡二叉树扩展而来 单key,范围,分页 O(Log(n) 除了数据,还多了左右指针,以及叶子节点指针 O(Log(n),需要调整树的结构,算法比较复杂
跳表 有序链表扩展而来 单key,分页 O(Log(n) 除了数据,还多了指针,但是每个节点的指针小于<2,所以比B+树占用空间小 O(Log(n),只用处理链表,算法比较简单

对LSM结构感兴趣的可以看下cassandra vs mongo (1)存储引擎

cassandra vs mongo (1)存储引擎

概括

存储引擎:

B-Tree

缓存管理

缓存管理的核心在于置换算法,置换算法常见的有FIFO(First In First Out),LRU(Least Recently Used)。关系型数据库在LRU的基础上,进行了改进,主要使用LIRS(Low Inter-reference Recency Set)
将缓存分为两级,第一次采用LRU,最近被使用到的数据会进第一级,如果数据在较短时间内被访问了两次或以上,则成为热点数据,进入第二级。避免了进行全表扫描的时候,可能会将缓存中的大量热点数据替换掉。

LSM

Log-Structured Merge Tree:结构化合并树,核心思想就是不将数据立即从内存中写入到磁盘,而是先保存在内存中,积累了一定量后再刷到磁盘中

LSM VS B-Tree

LSM在B-Tree的基础上为了获取更好的写性能而牺牲了部分的读性能,同时利用其它的实现来弥补读性能,比如boom-filter.

1.写

B树的写入,是首先找到对应的块位置,然后将新数据插入。随着写入越来越多,为了维护B树结构,节点得分裂。这样插入数据的随机写概率就会增大,性能会减弱。

LSM 则是在内存中形成小的排好序的树,然后flush到磁盘的时候不断的做merge.因为写入都是内存写,不写磁盘,所以写会很高效。

2.读

B树从根节点开始二分查询直到叶子节点,每次读取一个节点,如果对应的页面不在内存中,则读取磁盘,缓存数据。

LSM树整个结构不是有序的,所以不知道数据在什么地方,需要从每个小的有序结构中做二分查询,找到了就返回,找不到就继续找下一个有序结构。所以说LSM牺牲了读性能。但是LSM之所以能够作为大规模数据存储系统在于读性能可以通过其他方式来提高,比如读取性能更多的依赖于内存/缓存命中率而不是磁盘读取。

Cassandra

Cassandra是一个写性能优于读性能的NoSql数据库,写性能好一个原因在于选择了LSM存储引擎。

Mongo

MMAPv1

Mongo 3.2以前默认使用MMAPv1存储引擎,是基于B-Tree类型的。

边界(padding)

MMAPv1 存储引擎使用一个叫做”记录分配”的过程来为document存储分配磁盘空间。MongoDB与Cassandra不同的是,需要去更新原有的document。如果原有的document空间不足,则需要将这个document移动到新的位置,更新对应的index。这样就会导致一些不必要的更新,和数据碎片。

为了避免出现上述情况,就有了边界的概念,就是为document预分配空间。但是这样就有可能造成资源的浪费。mongo 按照64M,128M,256M…2G的2的冥次方递增策略预分配,最大2G。在数据量小的情况下问题并不明显,但是当达到2G时,磁盘占用量大的问题就出来了。

同样这一点和关系型数据库也不一样,关系型数据库对于长记录数据会分开存储。

锁

MMAPv1使用collection级别的锁,即一个collecion增,删,改一次只能有一个。在并发操作时,就会造成等待。

WiredTiger

3.2及其以后的默认存储引擎,同样是基于B-Tree的。采用了lock-free,风险指针等并发技术,使得在多核机器上工作的更好。

锁级别为document。并且引入了compression,减少了磁盘占用。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。


  • 上一条:
    Linux服务器安装Redis教程
    下一条:
    CentOS 安装redis和MySQL
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 在Redis中能实现的功能、常见应用介绍(0个评论)
    • 2024年Redis面试题之一(0个评论)
    • 在redis缓存常见出错及解决方案(0个评论)
    • 在redis中三种特殊数据类型:地理位置、基数(cardinality)估计、位图(Bitmap)使用场景介绍浅析(2个评论)
    • Redis 删除 key用 del 和 unlink 有啥区别?(1个评论)
    • 近期文章
    • 在go+gin中使用"github.com/skip2/go-qrcode"实现url转二维码功能(0个评论)
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • 在go + gin中gorm实现指定搜索/区间搜索分页列表功能接口实例(0个评论)
    • 在go语言中实现IP/CIDR的ip和netmask互转及IP段形式互转及ip是否存在IP/CIDR(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2017-12
    • 2020-03
    • 2020-05
    • 2021-04
    • 2022-03
    • 2022-05
    • 2022-08
    • 2023-02
    • 2023-04
    • 2023-07
    • 2024-01
    • 2024-02
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客