摘要：知识点中一般支持以下几种常见的索引树索引全文索引哈希索引我们今天重点来讲下树索引，以及为什么要用树来作为索引的数据结构。平衡二叉树定义首先符合二叉查找树的定义，另外任何节点的两个子树高度最大差为。
前言
讲到索引，第一反应肯定是能提高查询效率。例如书的目录，想要查找某一章节，会先从目录中定位。如果没有目录，那么就需要将所有内容都看一遍才能找到。
索引的设计对程序的性能至关重要，若索引太少，对查询性能受影响；而如果索引太多，则会影响增/改/删等的性能。
知识点MySQL中一般支持以下几种常见的索引：
B+树索引
全文索引
哈希索引
我们今天重点来讲下B+树索引，以及为什么要用B+树来作为索引的数据结构。
B+树索引并不能直接找到具体的行，只是找到被查找行所在的页，然后DB通过把整页读入内存，再在内存中查找。
重温数据结构 1.1 哈希结构如有 3、1、2、10、9、0、4、6这8个数据，建立如图1-1所示哈希索引。
直接查询：现在要从8个数中查找6这条记录，只需要计算6的哈希值，便可快速定位记录，时间复杂度为O(1)。
范围查询：如果要进行范围查询（大于4的数据），那这个索引就完全没用了。
1.2 二叉树查找树
二叉树是一种经典的数据结构，要求左子树小于根节点，右子树大于根节点。
如有 3、1、2、10、9、0、4、6这8个数据，建立如图1-2所示二分查找树。
直接查询：假设查找键值为6的记录，先找到根4，4<6，因此查找4的右子树，找到9；9大于6，因此查找9的左子树；一共查找3次。但如果顺序查找，则需要查找8次（位于最后）。
范围查询：如果需要查找大于4的数据，则遍历4的右子树就行了。
1.3 平衡二叉树（AVL树）
按照二叉查找树的定义，它是可以任意的构造，同样是这些数字，可以按照图1-3-1的方式来建立二叉查找树。同样查找数据6，需要查找5次。
因此为了最大性能地构造一个二叉查找树，需要它是平衡的，即平衡二叉树。
平衡二叉树定义：首先符合二叉查找树的定义，另外任何节点的两个子树高度最大差为1。
平衡二叉树的查询速度是很快的，但是有缺点：
维护树的代价是非常大，在进行插入或更新时，经常会需要多次左旋或右旋来维持平衡。如图1-3-2所示
数据量多的时候，树会很高，需要多次I/O操作。
在进行范围查找时，假设查找>=3，先找到3，然后需要查找到3的父节点，然后遍历父节点的右子树。
1.4 B+ 树
在B+树中，所有记录节点存放在叶子节点上，且是顺序存放，由各叶子节点指针进行连接。如果从最左边的叶子节点开始顺序遍历，能得到所有键值的顺序排序。
如有 3、1、2、10、9、0、4、6这8个数据，可建立如图1-4-1所示高度为2的B+树。
在进行更新时，B+树同样需要类似二叉树的旋转操作。举例，假设新增一个7，那可以直接填充到4、6的后面。如果再添加8，那么就需要进行旋转了，感受下面的B+树旋转过程。
采用B+树的索引结构优点：
B+树的高度一般为2-4层，所以查找记录时最多只需要2-4次IO，相对二叉平衡树已经大大降低了。
范围查找时，能通过叶子节点的指针获取数据。例如查找大于等于3的数据，当在叶子节点中查到3时，通过3的尾指针便能获取所有数据，而不需要再像二叉树一样再获取到3的父节点。
原文链接
未完待续…
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/7014.html
摘要：哈希索引也不支持多列联合索引的最左匹配规则。树索引的关键字检索效率比较平均，不像树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。 B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。 B+树 B+树是为磁盘及其他存储辅助设备而设计一种平衡查找树（不是二叉树）。B+树中，所有...
摘要：如果我们要进行范围查找，例如查找为的人，哈希表同样不支持，只能遍历全表。索引字段通过哈希映射成哈希码，如果很多字段都刚好映射到相同值的哈希码的话，那么形成的索引结构将会是一条很长的链表，这样的话，查找的时间就会大大增加。MySQL 索引你真的懂吗？这几道题带你了解索引的几个重要知识点 1. 什么是最左前缀原则？ 以下回答全部是基于MySQL的InnoDB引擎 例如对于下面这一张表 sh...
摘要：用户态不能干扰内核态所以指令就有两种特权指令和非特权指令不同的状态对应不同的指令。非特权指令所有程序均可直接使用。用户态常态目态执行非特权指令。 这是我今年从三月份开始，主要的大厂面试经过，有些企业面试的还没来得及整理，可能有些没有带答案就发出来了，还请各位先思考如果是你怎么回答面试官？这篇文章会持续更新，请各位持续关注，希望对你有所帮助！ 面试清单 平安产险 飞猪 上汽大通 浩鲸科...
摘要：为程序员金三银四精心挑选的余道面试题与答案，欢迎大家向我推荐你在面试过程中遇到的问题我会把大家推荐的问题添加到下面的常用面试题清单中供大家参考。 为Java程序员金三银四精心挑选的300余道Java面试题与答案，欢迎大家向我推荐你在面试过程中遇到的问题,我会把大家推荐的问题添加到下面的常用面试题清单中供大家参考。 前两天写的以下博客，大家比较认可，热度不错，希望可以帮到准备或者正在参加...
摘要：虽然有了十全的计划，但如何高效率去记住上面那么多东西是一个大问题，看看我是怎么做的。 前言 前一篇文章讲述了我在三月份毫无准备就去面试的后果，一开始心态真的爆炸，但是又不服气，一想到每次回来后家人朋友问我面试结果的期待脸，越觉得必须付出的行动来证明自己了。 面经传送门：一个1年工作经验的PHP程序员是如何被面试官虐的？ 下面是我花费两个星期做的准备，主要分三部分： 有计划——计划好...
阅读 3273·2023-04-25 14:57
阅读 2368·2021-11-22 14:56
阅读 1825·2021-09-29 09:45
阅读 1552·2021-09-22 15:53
阅读 3059·2021-08-25 09:41
阅读 781·2019-08-29 15:22
阅读 3175·2019-08-29 13:22
阅读 3001·2019-08-29 13:08
