3)查询效率比较稳定,因为每次查询都是从根节点到叶子节点,且为树的高度。
6、为何使用 B+ 树而非二叉查找树做索引?
我们知道二叉树的查找效率为 O(logn),当树过高时,查找效率会下降。另外由于我们的索引文件并不
小,所以是存储在磁盘上的。
文件系统需要从磁盘读取数据时,一般以页为单位进行读取,假设一个页内的数据过少,那么操作系统
就需要读取更多的页,涉及磁盘随机 I/O 访问的次数就更多。将数据从磁盘读入内存涉及随机 I/O 的访
问,是数据库里面成本最高的操作之一。
因而这种树高会随数据量增多急剧增加,每次更新数据又需要通过左旋和右旋维护平衡的二叉树,不太
适合用于存储在磁盘上的索引文件。
7、为何使用 B+ 树而非 B 树做索引?
在此之前,先来了解一下 B+ 树和 B 树的区别:
B 树非叶子结点和叶子结点都存储数据,因此查询数据时,时间复杂度最好为 O(1),最坏为 O(log
n)。而 B+ 树只在叶子结点存储数据,非叶子结点存储关键字,且不同非叶子结点的关键字可能重
复,因此查询数据时,时间复杂度固定为 O(log n)。
B+ 树叶子结点之间用链表相互连接,因而只需扫描叶子结点的链表就可以完成一次遍历操作,B
树只能通过中序遍历。
为什么 B+ 树比 B 树更适合应用于数据库索引?
B+ 树减少了 IO 次数。
由于索引文件很大因此索引文件存储在磁盘上,B+ 树的非叶子结点只存关键字不存数据,因而单个页
可以存储更多的关键字,即一次性读入内存的需要查找的关键字也就越多,磁盘的随机 I/O 读取次数相
对就减少了。
B+ 树减少了 IO 次数。
由于数据只存在在叶子结点上,所以查找效率固定为 O(log n),所以 B+ 树的查询效率相比B树更加稳
定。
B+ 树更加适合范围查找
B+ 树叶子结点之间用链表有序连接,所以扫描全部数据只需扫描一遍叶子结点,利于扫库和范围查
询;B 树由于非叶子结点也存数据,所以只能通过中序遍历按序来扫。也就是说,对于范围查询和有序
遍历而言,B+ 树的效率更高。
ref
为什么
B+
树比
B
树
更
适
合
应
用
于
数据
库
索
引
?
8、什么是最左匹配原则?
顾名思义,最左优先,以最左边为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、
between、like)就会停止匹配。
如建立 (a,b,c,d) 索引,查询条件 b = 2 是匹配不到索引的,但是如果查询条件是 a = 1 and b =
2 或 a=1 又或 b = 2 and a = 1 就可以,因为优化器会自动调整 a,b 的顺序。
再比如 a = 1 and b = 2 and c > 3 and d = 4 ,其中 d 是用不到索引的,因为 c 是一个范围查
询,它之后的字段会停止匹配。
最左匹配的原理