沈阳高端网站建设公司,一般做网站费用,360建筑工程网,泰安网络推广平台摘要面试时#xff0c;交流有关mysql索引问题时#xff0c;发现有些人能够涛涛不绝的说出B树和B树#xff0c;平衡二叉树的区别#xff0c;却说不出B树和hash索引的区别。这种一看就知道是死记硬背#xff0c;没有理解索引的本质。本文旨在剖析这背后的原理#xff0c;欢…摘要面试时交流有关mysql索引问题时发现有些人能够涛涛不绝的说出B树和B树平衡二叉树的区别却说不出B树和hash索引的区别。这种一看就知道是死记硬背没有理解索引的本质。本文旨在剖析这背后的原理欢迎留言探讨问题如果对以下问题感到困惑或一知半解请继续看下去相信本文一定会对你有帮助mysql 索引如何实现mysql 索引结构B树与hash有何区别。分别适用于什么场景数据库的索引还能有其他实现吗redis跳表是如何实现的跳表和B树LSM树有和区别呢解析首先为什么要把mysql索引和redis跳表放在一起讨论呢因为他们解决的都是同一种问题用于解决数据集合的查找问题即根据指定的key快速查到它所在的位置(或者对应的value)当你站在这个角度去思考问题时还会不知道B树索引和hash索引的区别吗数据集合的查找问题现在我们将问题领域边界划分清楚了就是为了解决数据集合的查找问题。这一块需要考虑哪些问题呢需要支持哪些查找方式单key/多key/范围查找插入/删除效率查找效率(即时间复杂度)存储大小(空间复杂度)我们看下几种常用的查找结构hashhash是key,value形式通过一个散列函数能够根据key快速找到valueB树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最近被使用到的数据会进第一级如果数据在较短时间内被访问了两次或以上则成为热点数据进入第二级。避免了进行全表扫描的时候可能会将缓存中的大量热点数据替换掉。LSMLog-Structured Merge Tree:结构化合并树核心思想就是不将数据立即从内存中写入到磁盘而是先保存在内存中积累了一定量后再刷到磁盘中LSM VS B-TreeLSM在B-Tree的基础上为了获取更好的写性能而牺牲了部分的读性能同时利用其它的实现来弥补读性能比如boom-filter.1.写B树的写入是首先找到对应的块位置然后将新数据插入。随着写入越来越多为了维护B树结构节点得分裂。这样插入数据的随机写概率就会增大性能会减弱。LSM 则是在内存中形成小的排好序的树然后flush到磁盘的时候不断的做merge.因为写入都是内存写不写磁盘所以写会很高效。2.读B树从根节点开始二分查询直到叶子节点每次读取一个节点如果对应的页面不在内存中则读取磁盘缓存数据。LSM树整个结构不是有序的所以不知道数据在什么地方需要从每个小的有序结构中做二分查询找到了就返回找不到就继续找下一个有序结构。所以说LSM牺牲了读性能。但是LSM之所以能够作为大规模数据存储系统在于读性能可以通过其他方式来提高比如读取性能更多的依赖于内存/缓存命中率而不是磁盘读取。CassandraCassandra是一个写性能优于读性能的NoSql数据库写性能好一个原因在于选择了LSM存储引擎。MongoMMAPv1Mongo 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增删改一次只能有一个。在并发操作时就会造成等待。WiredTiger3.2及其以后的默认存储引擎,同样是基于B-Tree的。采用了lock-free,风险指针等并发技术使得在多核机器上工作的更好。锁级别为document。并且引入了compression减少了磁盘占用。总结以上就是这篇文章的全部内容了希望本文的内容对大家的学习或者工作具有一定的参考学习价值谢谢大家对脚本之家的支持。您可能感兴趣的文章:新手学习MySQL索引由不同的索引更新解决MySQL死锁套路通过唯一索引S锁与X锁来了解MySQL死锁套路分享几道关于MySQL索引的重点面试题Mysql中的索引精讲MySQL学习(七)Innodb存储引擎索引的实现原理详解使用shell脚本来给mysql加索引的方法MySQL批量插入和唯一索引问题的解决方法高效利用mysql索引指南
