草庐IT

【MySQL】—— 数据库索引 (索引是什么？B树，B+树)

Perceus 2023-03-28 原文
(目录)

索引

1.什么是数据库索引?

1.1 概念

  • 索引是一种特殊的文件，包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引，并指定索引的类型，各类索引有各自的数据结构实现。
索引（index）可以说是一本书的目录（index）。【两者的英文是同一个只是表现的形式不一样。】

1.2 作用

  1. 数据库中的表、数据、索引之间的关系，类似于书架上的图书、书籍内容和书籍目录的关系。
  2. 索引所起的作用类似书籍目录，可用于快速定位、检索数据。
  3. 如果没有索引,在数据库中进行查找就要把整个表遍历一遍,很耗时.
  4. 索引对于提高数据库的性能 (主要是提高查找效率,修改增加删除效率还会有所下降) 有很大的帮助。
  5. 本质上索引就是为了避免数据库进行顺序查找,提高查找效率.

1.3 使用场景

要考虑对数据库表的某列或某几列创建索引，需要考虑以下几点：

  1. 数据量较大，且经常对这些列进行条件查询。
  2. 该数据库表的插入操作，及对这些列的修改操作频率较低。
  3. 索引会占用额外的磁盘空间。(用空间效率换取时间效率) 满足以上条件时，考虑对表中的这些字段创建索引，以提高查询效率。 反之，如果非条件查询列，或经常做插入、修改操作，或磁盘空间不足时，不考虑创建索引。

1.4 索引的优缺点

思考一个问题：

树的目录一旦决定了，后续每次对书的内容进行调整时，都可能会印象到目录的准确性，就需要重新调整目录。   数据库的索引也是一样的情况：

当我们 对 数据进行“增删改”操作的时候，往往也需要同步调整索引的结构。   索引带来的好处:提高了查询效率 索引带来的坏处：占用了更多的空间，拖慢了增删查改的速度。

从表面来上看，似乎索引的坏处 比 索引带来的好处要多。但！这不必意味着 弊大于利！！ 因为在实际需求的场景中，查询操作往往是最高频率的操作。 相对于“增删改” 的使用频率则低的可怜。 因此，查询作为一个高频操作，索引对其来说是不可缺少，   另外，有索引之后对于查询的效率的提升使非常巨大！！！ 当MySQL里面的数据量级 达到千万级别的时候（一个表里就有几千万，甚至破亿的数据）再去遍历表，就会非常非常的低效！！！   在另一方面：

MySQL在进行数据比较的时候，不是像我们编程那样，一个for循环（这样的想法是错误的）

编程上的查询是在内存中的比较；MySQL中的比较是在硬盘上比较。 也就是说：在MySQL中的每一次比较都会涉及到硬盘的 IO 操作。

又因为硬盘的 IO 的 访问速度 比 内存 慢 3 ~ 4 个数量级（几千~万倍）。 所以，如果是查询的操作更是慢上加慢！！！ 【这里又一次体现了索引的好处：能使这里的查找效率提高数倍】

1.5 如何使用

  • 创建主键约束（PRIMARY KEY）、唯一约束（UNIQUE）、外键约束（FOREIGN KEY）时，会自动创建对应列的索引。

查看索引

命令格式：show index from 表名;

show index from student; 其作用：查看一个数据表上都有哪些索引

创建索引

命令格式：

create index 索引名字 on 表名（列名）

注意：

创建索引这件事是一个非常低效的事情，尤其是当前表里面已经有很多数据的时候。 它需要给该列的每一行数据都设置一个索引，因此在数据量庞大的情况下，创建的索引的过程是非常耗时的！

因此，以后在工作的时候，看到某个数据库的一个表没有索引，千万不要贸然去创建一个索引 你啪的回车一敲，下一秒数据库就挂了。

操作数据库本身就是一个危险操作。必须时刻小心谨慎。

删除某个表中的索引

命令格式：

drop index 索引名字 on 表名

删除索引操作和创建同理，都是非常低效的事情，也容易让数据库挂了

2.索引的数据结构是什么?

2.1 可以是二叉搜索树或者红黑树吗?

  • 不可以
  1. 二叉搜索树的平均查找效率是O(logN)
  2. 如果数据很多的话,二叉搜索树最多俩个分支,所以树的深度会很大,查找效率其实不高
  3. 如果是查找范围的时候还需要对二叉搜索树进行中序遍历 (因为二叉搜索树中序遍历是有序序列) 又不是很高效O(N)

2.2 可以是哈希表吗?

  • 不可以
  1. 如果是处理相等情况,哈希表很高效
  2. 但是哈希表不可以处理其他逻辑,比如范围查找 > >= < <= between and
  3. 因为哈希的查找是把key带入哈希函数得到下标,再根据下标取对应的链表,再去遍历链表比较key是否相等,无法进行范围查找

2.3 可以是B树吗?

  • 本质可以,但为了更高的效率不选它
B树与二叉树差异：

  1. 为了结点不是2叉而是N叉
  2. 为了结点不是存储一个数据,而是可能存储多个数据
  3. 每个节点存储数据的个数和该节点的度是有关系的 度=存储数据的个数+1
  4. 此时在B树上查找就是一个N分查找,效率比二叉树还高
  5. 由于每个及节点存储了多个数据,每个节点又有多个度,所以和二叉树相比,B树的高度会低很多,查找起来效率一会高一下.而且简单的范围查找会容易一些.
在整个数据量的条件一定的情况下，N叉搜索树的高度 一定比 二叉搜索树要低。 在数据库中使用的这个多叉树，又不太一样，是一个很特殊的树，我们称为 B+ 树。 【B+ 树 是 数据库中最常见的数据结构】 注意！数据库有很多种，每个数据库底层又支持多种存储引擎 这些存储引擎实现了数据库具体按照什么结构来存储的程序。 那么就意味着 每个存储引擎 存储数据的结构 可能都不一样，背后的索引数据结构可能也不同。 所以，这里面可能会有很多种多叉树来去表示这里的数据结构。 只是 B+ 树 是 最常用的一种数据结构。 那么，B+ 树 又是什么样子的？ 想要 理解 B+ 树，需要先理解它的前身 B 树（ B-树：这个是B树的另一种写法，而不是B减树）

2.4 可以是B+树吗?

与B-树相比的差异：

  1. 每一层的元素之间都链接在一起
  2. 数据(表的一行记录)只存在叶子节点上,非叶子节点只保存一些辅助查找的边界信息
  3. 查询任一条记录都比较平均,不会出现效率差异很大的情况
  4. 不需要额外进行中序遍历,遍历叶子节点就是中序结果,所以处理范围查找很高效
  5. 叶子放在磁盘上,非叶子放在内存中,减少了访问磁盘的次数,查找也就更高效了,而且索引在内存中实际开销有不高
  6. 索引引起的效果就是加快查找效率, 减慢插入删除修改的效率 (因为需要同步调整索引结果)
  7. 索引也会占用额外空间(本质上使用空间换取时间)
  8. 给具体表中某列加索引的时候,加在主键的索引和加在其他列的索引是截然不同的.
  9. 主键索引的叶子结点value存的是表的一行完整数据, 其他索引的叶子节点value只存的是主键的信息(如id)
因为B树 是 B+树的前身，那么B+树想对比B树又做出了那些改变？

疑问：为什么B+树这么去构建？

你可以这么认为 B+ 树 就是为了 数据库索引量身打造的！！！！

  1. 使用B+树进行查找的时候，整体IO次数也是比较少的。
  2. 所有的查询最终多会落在叶子结点上，每次查询的 IO 次数都是差不多的，故查询的速度是稳定的，相差不大。
  3. 叶子结点用链表链接之后，非常适合进行范围查找
  4. 所有的数据存储（数据又称载荷）都是放到叶子结点上的。也就是说非叶子结点中只需要保存key值就可以了。因此非叶子节点整体占用空间较小，甚至可以加载到内存中。（一旦能够全部放在内存里，此时硬盘上的IO次数几乎就为零了）
例如：

找到 大于等于5，且小于等于 11 的值。

所有的数据存储（数据又称载荷）都是放到叶子结点上的。也就是说非叶子结点中只需要保存key值就可以了。因此非叶子节点整体占用空间较小，甚至可以加载到内存中。（一旦能够全部放在内存里，此时硬盘上的IO次数几乎就为零了）

总结

mdashMySQLcodestrongli索引B+树B树数据库MySQL数据库

有关【MySQL】—— 数据库索引 (索引是什么？B树，B+树)的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  3. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  4. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  5. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  6. ruby - ruby 中的 TOPLEVEL_BINDING 是什么？ - 2

    它不等于主线程的binding，这个toplevel作用域是什么？此作用域与主线程中的binding有何不同？>ruby-e'putsTOPLEVEL_BINDING===binding'false 最佳答案 事实是，TOPLEVEL_BINDING始终引用Binding的预定义全局实例，而Kernel#binding创建的新实例>Binding每次封装当前执行上下文。在顶层，它们都包含相同的绑定(bind)，但它们不是同一个对象，您无法使用==或===测试它们的绑定(bind)相等性。putsTOPLEVEL_BINDINGput

  7. ruby - Infinity 和 NaN 的类型是什么？ - 2

    我可以得到Infinity和NaNn=9.0/0#=>Infinityn.class#=>Floatm=0/0.0#=>NaNm.class#=>Float但是当我想直接访问Infinity或NaN时:Infinity#=>uninitializedconstantInfinity(NameError)NaN#=>uninitializedconstantNaN(NameError)什么是Infinity和NaN？它们是对象、关键字还是其他东西？ 最佳答案 您看到打印为Infinity和NaN的只是Float类的两个特殊实例的字符串

  8. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  9. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  10. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

随机推荐