数据结构---B+Tree

简介: 数据结构---B+Tree


B+Tree

在我没了解B+Tree之前,听别人提到这个词时,脑子一片空白,懵懵的,今天利用空闲时间,简单了解了一下B+Tree,下面来简单认识一下B+Tree吧!

简单了解一下B+Tree

B+Tree:是为磁盘等外存储设备设计的一种平衡查找树。

他的存储特点有哪些呢?

存储特点

子叶节点存储Data(data元素地址指针位置等),非叶子节点存储索引

叶子节点用指针连接,提高区间访问性能

根据下面这幅图我简单介绍一下

Mysql给每个叶子节点设置大小为16K;

以数值15为例,一般ID都会使用bigint类型,大概会分配8Bigint字节,(数值15旁边的空格为)磁盘地址指针大概会分配6Bitint字节;

以两千万数据为例,高度为3的B+tree数据结构;

叶子节点大概可以存放1170个元素;

非叶子节点可以存放16个元素;

IO读写操作只需要2-3次,即可查询到要查询的数据。

折半查找

看下图:

非叶子结点会提前直接加载到内存中,例如要查找20的索引,前面定位两次非叶子节点都是在内存中查找,不需要和磁盘进行IO操作,进行折半查找,只需要叶子节点进行一次的IO操作,把磁盘数据加载到内存。

MySQL表数据文件

test_myisam.frm FRM文件 存储的表结构文件

test_myisam.MYD MYD文件 存储引擎

test_myisam.NYI NYI文件 数据文件索引文件

MyISAM存储引擎和InnoDB存储引擎的区别?

主要是在叶子节点。

MyISAM存储引擎

叶子节点存储的是地址指针的位置

非聚集索引(索引和数据没有放在一个文件里,索引和数据没有聚集在一个文件)

InnoDB存储引擎

叶子节点存储的是地址指针位置对应的节点值

聚集索引(索引和数据放在一个文件里,索引和数据聚集放在一个文件)

目录
相关文章
|
8月前
|
存储 分布式数据库 C语言
【初阶数据结构】树(tree)的基本概念——C语言
【初阶数据结构】树(tree)的基本概念——C语言
|
10天前
|
存储 算法 关系型数据库
MySQL索引 索引数据结构B+Tree、分类及使用、回表查询
MySQL索引 索引数据结构B+Tree、分类及使用、回表查询
113 0
|
6月前
|
存储 Linux 编译器
打破常规,Linux内核新的数据结构上场maple tree(上)
打破常规,Linux内核新的数据结构上场maple tree
|
算法
数据结构和算法(树Tree)
树 概述: 树: 是一种经常用到的数据结构,用来模拟具有树状结构性质的数据集合。 树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看,树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。 二叉树: 是一种更为典型的树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。 树的遍历 前序遍历 前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。 中序遍历 中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。 我们可以通过中序遍历得到一个递增的有序序列 后序遍历 后序遍历是先遍历左子树,然后遍历右子树,最后访
146 0
|
存储 关系型数据库 MySQL
mysql索引(二)索引的数据结构B+TREE
索引本质上是一种数据结构,让我们在查询数据的时候尽量减少磁盘I/O。 前边大概看了索引的原理。数据库的复杂性,以及读取磁盘时,磁盘I/O等。任何一种数据结构都不是凭空产生的,一定会有它的背景和使用场景,我们现在总结一下,我们需要这种数据结构能够做些什么,其实很简单,那就是:每次查找数据时把磁盘IO次数控制在一个很小的数量级,最好是常数数量级。
136 0
mysql索引(二)索引的数据结构B+TREE
|
存储 索引
数据结构-B+tree
B+ 树是 B 树的扩展,它允许高效的插入、删除和搜索操作。 在 B 树中,键和记录都可以存储在内部节点和叶节点中。而在 B+ 树中,记录(数据)只能存储在叶子节点上,而内部节点只能存储键值。 B+树的叶子节点以单链表的形式链接在一起,使搜索查询更加高效。 B+树用于存储无法存储在主存储器中的大量数据。由于主存的大小总是有限的,B+树的内部节点(访问记录的键)存储在主存中,而叶节点存储在辅助内存中。
146 0
|
存储 搜索推荐 算法
数据结构(五):哈夫曼树(Huffman Tree)
哈夫曼树 哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,所以也称之为最优二叉树。 节点的带权路径长指的是叶子节点的权值与路径长的乘积,树的带权路径长即为树中所有叶子节点的带权路径长度之和。
1861 0
|
存储 Python
数据结构(二):二叉搜索树(Binary Search Tree)
二分法猜数字的游戏应该每个人都知道,通过对猜测数字“大了”、“小了”的情况判断,来猜出最终的数字。序列范围为 的集合,复杂度为 ,即最多需要 次可以猜到最终数字。
1590 0