数据库基础知识整理实验报告（数据库技术基础实验分析及小结）



该篇只是针对一个视频的学习后的总结，内容不是非常的全面，不过也可以让我们拾起一些记忆。

本篇主要围绕以下几个问题来说明：

1、什么是索引？

2、索引的作用与本质？

3、索引都有哪些算法？

4、Mysql中索引是如何存储的？

5、为什么普通索引中的叶子节点中只存储id和name？

什么是索引？

  索引是帮助快速检索出数据的数据结构。举个例子：你去图书馆找书，首先会根据目录去找到对应的书架，然后找到你想要的那本书。如果没有目录，图书馆的书有成千上万，你需要一本一本的找，岂不是把人给累死，所以这就是索引的好处。

索引的作用与本质：

作用：快速检索

本质：数据结构+算法

常见的数据结构有：数组、链表、图、树、队列……

那么，数据结构的本质是什么呢？答案：存储数据

索引都有哪些算法：

  哈希散列法、二叉树、红黑树、B-Tree、B+Tree

哈希散列法：

  题外话：InnoDB默认使用了自适应hash算法，当你使用等值查询，达到一定阈值后，会使用这种算法【eg:select * from table where name=‘张三’】

优点：最好时间复杂度是O(1)，能够快速检索

缺点：不支持范围查找

二叉树：

优点：平均复杂度均为O(logn)

缺点：当插入的值比之前大，会导致二叉树倾斜，平均复杂度为O(n)

红黑树：

特点：

① 每个节点或者是黑色，或者是红色；

② 根节点是黑色；

③ 每个为空的叶子节点是黑色；

④ 如果一个节点是红色的，则它的子节点必须是黑色的；

优点：相对平衡、平均复杂度均为O(logn)

缺点：跟二叉树一样，也会存在倾斜，只不过是对二叉树的一个小改进

B-Tree：

特点：

  B-Tree是为磁盘等外存储设备设计的一种平衡查找树。【画外音：系统从磁盘读取数据到内存时，是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么】。

  InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16kb。

优点：B树相对二叉树虽然提高了磁盘IO性能

缺点：并没有解决遍历元素效率低下的问题。每个节点中既要存索引信息，又要存其对应的数据，如果数据很大，那么当树的体量很大时，每次读到内存中的树的信息就会不太够

B+Tree：

  B+树相比B树，本质上是一样的，区别就在与B+树的所有根节点都不带有任何数据信息，只有索引信息，所有数据信息全部存储在叶子节点里，这样，整个树的每个节点所占的内存空间就变小了，读到内存中的索引信息就会更多一些，相当于减少了磁盘IO次数，这样就解决了每次读到内存中的树的信息不太够的问题。

  又由B树的性质可以得到，所有叶子节点都会在同一层，B+树会以一个链表的形式将所有叶子节点的信息全部串联起来，这样，想遍历所有数据信息只需要顺序遍历叶子节点就可以了，方便又高效，这样就解决了遍历元素效率低下的问题。

  不仅如此，B+树还有一个相应的优质特性，就是B+树的查询效率是非常稳定的，因为所有信息都存储在了叶子节点里面，从根节点到所有叶子节点的路径是相同的。

优点：磁盘读写代价更低、数据信息遍历更加方便、查询效率更加稳定

Mysql中索引是如何存储的:

  对于InnoDB来说，它有两个文件：user.ibd、user.frm，【.ibd是索引文件、.frm是数据结构类型】；

  对于Myisam来说，它有三个文件：user.myi、user.myd、user.frm，【.myi是索引文件、.myd是数据文件、.frm是数据结构类型】

为什么普通索引中的叶子节点中只存储id和name？

  因为，为了减少磁盘空间的占用，如果你每个普通索引的叶子节点都存储整行数据，索引越多所占用的磁盘空间越多，而且你存储聚簇索引的地址，查询整行的数据效率也不会很差。普通索引通过id去查询整行记录的这个过程通常叫回表。

上述算法生成地址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/sjkxydsj/64875.html