发布时间:2023-05-02 08:30
数据库最常用的两个功能就是“等值查询”和“范围查询”。如果只是为了满足“等值查询”,那么Hash散列表和平衡二叉查找树都能胜任数据库索引这个使用场景,但是“范围查询”却加大了难度,使得它们不太适合了。
在原先讲过的“跳表”倒是很契合,但实际场景中,大家都是使用的B+树。
二叉树我们前面也都了解过了,我们来看下,用它来作为索引的数据结构会存在什么问题?首先它是能够满足“等值查询”的,但是无法进行“范围查询”,所以,我们需要对其进行改造:
改造前后的二叉树结构示意图如下:
改造后的好处是:
看上去还不错,但是实际使用时有问题,因为我们数据库中需要存储的数据实在是非常多,如果使用这样的改造后的二叉树,树的高度将是非常惊人的。不但查找起来非常缓慢,而且这么多节点全部加载到内存中也是不现实的。
我们再次进行如下的改造:
改造后的数据结构示意图如下:
改造后的好处是:
但同时也有部分缺点:
B+树是在B树的基础上改进的,B树中每个节点是存储真实的数据的,所以整个树会很大;B树的叶子节点是没有用链表串联的,所以还是无法满足范围查找的场景;因此,B树其实就是一个子节点不能小于m/2的m叉树;
B+树和B树的关系,以及MySQL中不同存储引擎数据结构的不同可以参考《【数据库专题】如何理解数据库的索引?》
zookeeper入门到精通04——zookeeper集群选举与集群操作
用java实现学生成绩管理系统_学生成绩管理系统(java实现)
2-4 经典机器学习算法-K近邻算法KNN,KNN与K-means之间的区别和联系,KNN平衡方差和偏差,Python实现KNN
Knowledge-Aware Graph-Enhanced GPT-2 for Dialogue State Tracking论文笔记
【机器学习系列】【调参GridsearchCV】随机森林、GBDT、LightGBM和XGBoost调参顺序,外加一些加速调参的小技巧(主要介绍坐标下降)