聊聊 MySQL 索引和 Redis 跳表

栏目: 数据库 · 发布时间: 5年前

内容简介:面试时,交流有关mysql索引问题时,发现有些人能够涛涛不绝的说出B+树和B树,平衡二叉树的区别,却说不出B+树和hash索引的区别。这种一看就知道是死记硬背,没有理解索引的本质。本文旨在剖析这背后的原理,欢迎留言探讨如果对以下问题感到困惑或一知半解,请继续看下去,相信本文一定会对你有帮助首先为什么要把mysql索引和redis跳表放在一起讨论呢,因为他们解决的都是同一种问题,用于

摘要

面试时,交流有关 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 聊聊 MySQL 索引和 Redis 跳表 hash是key,value形式,通过一个散列函数,能够根据key快速找到value B+树 聊聊 MySQL 索引和 Redis 跳表 B+树是在平衡二叉树基础上演变过来,为什么我们在算法课上没学到B+树和跳表这种结构呢。因为他们都是从工程实践中得到,在理论的基础上进行了妥协。

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

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

总结

聊聊 MySQL 索引和 Redis 跳表

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

有用点好看,谢谢

参考

https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7545940.html


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

自流量生活

自流量生活

斯科特·福克斯(Scott Fox) / 王晶晶 / 中信出版社 / 2018-8-1

一位远嫁他国的平凡女孩,陌生的环境、陌生的语言……她不得不从头学起。有写作爱好的她在网络上记录着她学习生活中的小故事。神奇的是,越来越多的人联系她,有人要付钱看新的故事,还有人想把这些故事拍成电视短片。她是怎么做到的? 这本书将告诉你如何利用互联网打造自己的“流量”生活,使你既能获取收入,又能以自己喜欢的方式过一生。在阅读这本书的过程中,你可能会找到自己喜欢的生活方式,了解成功打造自身“流量......一起来看看 《自流量生活》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具