慈溪网站制作哪家最便宜,长沙做官方网站,广东省农业农村厅领导名单,想创业去哪里找项目首先#xff0c;能作为索引的数据结构有很多#xff0c;例如数组、链表、二叉树 数据和索引都是存储在磁盘里的。 我们通过索引来查询数据时#xff0c;先从磁盘读取索引到内存#xff0c;再通过索引从磁盘中找到某行数据#xff0c;然后读入到内存。 要设计一个适合 MySQ…首先能作为索引的数据结构有很多例如数组、链表、二叉树 数据和索引都是存储在磁盘里的。 我们通过索引来查询数据时先从磁盘读取索引到内存再通过索引从磁盘中找到某行数据然后读入到内存。 要设计一个适合 MySQL 索引的数据结构至少满足以下要求 能在尽可能少的磁盘的 I/O 操作中完成查询工作要能高效地查询某一个记录也要能高效地执行范围查找 数组 优点用数组可以实现二分查找时间复杂度从On降到Ologn 缺点 每次查找都要不断计算中间的位置。但是插入新元素的时候性能太低。元素之后的所有元素后移一位 二叉搜索树 优点解决了数组的2个缺点 每次查找只需要作比较即可插入新元素时可以任意位置插入不需要将之后元素所有后移一位。 缺点 当每次插入的元素都是二叉查找树中最大的元素二叉查找树就会退化成了一条链表查找数据的时间复杂度变成了 O(n)每访问一次节点都要与磁盘进行一次IO操作。而树的高度就时访问节点的次数二叉树的高度太容易高了所以增加了IO。 自平衡二叉树 优点 解决了二叉查找树就会退化成了一条链表的问题 缺点 高度问题依旧存在 需要解决高度问题首先想到将二叉树变为M叉树由此想到了B树 B树 优点 解决了高度问题 缺点 但是 B 树的每个节点都包含数据索引记录而用户的记录数据的大小很有可能远远超过了索引数据这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。 而且在我们查询位于底层的某个节点比如 A 记录过程中「非 A 记录节点」里的记录数据会从磁盘加载到内存但是这些记录数据是没用的我们只是想读取这些节点的索引数据来做比较查询而「非 A 记录节点」里的记录数据对我们是没用的这样不仅增多磁盘 I/O 操作次数也占用内存资源。 如果使用 B 树来做范围查询的话需要使用中序遍历这会涉及多个节点的磁盘 I/O 问题从而导致整体速度下降。 B树 优点 B树的非叶子节点可以存放更多的索引在数据量相同的情况下B树会比B树的高度更低。B 树有许多冗余节点而B树没有这就使得B树的插入和删除效率更高B 树所有叶子节点间还有一个链表进行连接可以据此进行范围的查询不用像B树一样只能遍历查询
