最全MySQL8.0实战教程 17 MySQL的索引 17.4 索引的原理【2 相关算法】

悠悠 2024-03-26 18:58 17阅读 0赞

#### 最全MySQL8.0实战教程 ####

#### 文章目录 ####

*   *   *  最全MySQL8.0实战教程
         *  17 MySQL的索引
         *   *  17.4 索引的原理【2 相关算法】
             *   *  17.4.2 Hash算法
                 *  17.4.3 二叉树
                 *  17.4.4 平衡二叉树
                 *  17.4.5 Btree树

[【黑马程序员MySQL知识精讲+mysql实战案例\_零基础mysql数据库入门到高级全套教程】 ][MySQL_mysql_mysql_]

#### 17 MySQL的索引 ####

##### 17.4 索引的原理【2 相关算法】 #####

###### 17.4.2 Hash算法 ######

![在这里插入图片描述][b675e0be76ed4b4fb9c9b3e882174694.png_pic_center]

\*\*优点：\*\*通过字段的值计算的hash值，定位数据非常快。

\*\*缺点：\*\*不能进行范围查找，因为散列表中的值是无序的，无法进行大小的比较。

###### 17.4.3 二叉树 ######

![在这里插入图片描述][1a8a757501474a1f8186c6ed6d1e1fd4.png_pic_center]

\*\*特性：\*\*分为左子树、右子树和根节点，左子树比根节点值要小，右子树比根节点值要大

\*\*缺点：\*\*有可能产生不平衡 类似于链表的结构 。

###### 17.4.4 平衡二叉树 ######

![在这里插入图片描述][8e4fbf560a36478c93985724b151d50a.png_pic_center]

**特点：**

*  它的左子树和右子树都是平衡二叉树
 *  左子树比中间小，右子树比中间值
 *  左子树和右子树的深度之差的绝对值不超过1

**缺点：**

*  插入操作需要旋转
 *  支持范围查询，但回旋查询效率较低，比如要查找大于8的，会回旋到父节点7、10。
 *  如果存放几百条数据的情况下，树高度越高，查询效率会越慢

###### 17.4.5 Btree树 ######

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，Btree结构可以有效的解决之前的相关算法遇到的问题。

![在这里插入图片描述][2f989cbde3274fe881eb57ee697dc6e4.png_pic_center]

数据结构可视化工具：[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html][https_www.cs.usfca.edu_galles_visualization_Algorithms.html]

![在这里插入图片描述][aa73e3c92fa54f94ae55571dfa195cba.png_pic_center]

![在这里插入图片描述][e082a3ba8960459299126f60ea6bdcd5.png_pic_center]

B-Tree

![在这里插入图片描述][7c609ee3594846a9af14027ac82e070e.png_pic_center]

B+Tree

![在这里插入图片描述][0c939e3e3e0c4b10a561240c863db862.png_pic_center]

B+ 的优势就在于叶子节点保存了所有的值。【不会丢】，而且在查询范围数据时，非常的快，不用像B- 树那样来回动，叶子节点中的数据好似链表，数据是连续 的。

这也是MySQL 选用B + 树做索引的优势。

[MySQL_mysql_mysql_]: https://www.bilibili.com/video/BV1iF411z7Pu
[b675e0be76ed4b4fb9c9b3e882174694.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1fceb711cc1746c5b127b799980e66ef.png
[1a8a757501474a1f8186c6ed6d1e1fd4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/00300c7b74b14f50ac365208ef90ece6.png
[8e4fbf560a36478c93985724b151d50a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/34d656ed33ce4547ac404f68d84cbfa2.png
[2f989cbde3274fe881eb57ee697dc6e4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e454f6a7ec2249c7930acf9b8ad55cf9.png
[https_www.cs.usfca.edu_galles_visualization_Algorithms.html]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[aa73e3c92fa54f94ae55571dfa195cba.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/21c940c89be147ecaf04d53dc5afa238.png
[e082a3ba8960459299126f60ea6bdcd5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4d5484255f444e8694425c0569c2a3db.png
[7c609ee3594846a9af14027ac82e070e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/816d128fd81b45e6931853448d11c093.png
[0c939e3e3e0c4b10a561240c863db862.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d8187dfac26a4c51a910d4b4f555b6f5.png