聊城制作手机网站公司,网站建设昆明哪家好,《学做网站论坛》视频下载,服装设计网站怎么做提示#xff1a;内容是读《MySQL技术内幕#xff1a;InnoDB存储引擎》#xff0c;笔记摘要 文章目录 二叉查找树平衡二叉树(AVL) B树(BTree)B树(BTree)InnoDB B树索引索引结构#xff08;InnoDB B树#xff09;B树存放的数据量 二叉查找树 在二叉查找树中#xff0c;左子…提示内容是读《MySQL技术内幕InnoDB存储引擎》笔记摘要 文章目录 二叉查找树平衡二叉树(AVL) B树(BTree)B树(BTree)InnoDB B树索引索引结构InnoDB B树B树存放的数据量 二叉查找树 在二叉查找树中左子树的键值总是小于根的键值右子树的键值总是大于根的键值因此可以通过中序遍历得到键值的排序输出。对上图进行中序遍历(左-根-右)后输出2、3、5、6、7、8。
平衡二叉树(AVL)
为解决二叉查找树数据左右分配不平衡出数据大面积分布存储在根节点左侧或右侧查询效率低的问题故引入平衡二叉查找树-AVL树。 平衡二叉树的定义 首先符合二叉查找树的定义; 其次必须满足任何节点的两棵子树的高度最大差为1。 平衡二叉树的缺点 平衡二叉树的查询速度的确快但是维护一棵平衡二叉树的存储成本有很大通常需要1次或多次左旋或右旋来得到经过插入或更新操作后二叉树的平衡性。 例如 平衡二叉树【 1、2、4、5、9】增加新数据节点3。
B树(BTree)
概念 B树和平衡二叉树不同B树属于多叉树又名平衡多路查找树查找路径不只两个数据库索引里大量使用者B-Tree和BTree的数据结构。 特点 1排序方式所有节点关键字是按递增次序排列并遵循左小右大原则 2子节点数非叶节点的子节点数范围(1,M] , 且M2空树除外 注M阶代表一个树节点最多有多少个查找路径当M3则是3叉树 3关键字数Key枝节点的关键字Key数量数据范围[ceil(M/2)-1,M-1] 注ceil()是个朝正无穷方向取整的函数 如3阶B树时ceil(1.5)结果为2关键字数范围[1,2]); 4所有叶子节点均在同一层、叶子节点包含关键字和数据; 5拥有n-1个key值非叶子节点必须有n个孩子节点 6一个节点的所有key值必须是升序排序的 BTree是单个节点可以存储多个键值和数据的多路平衡查找树。 在存储海量的数据因为平衡二叉树的每个节点只存储一个键值和数据节点将会非常多且高度也其高当查找数据时会进行很多次磁盘IO查找的效率将会极低为了解决平衡二叉树的这个弊端需要一种单个节点可以存储多个键值和数据的平衡树BTree
B树(BTree)
概念 B树是B树的一个进化相对于B树来说B树更充分的利用了节点的空间让查询速度更加稳定其速度完全接近于二分法查找。结构如下 特点 1非叶子节点只存储索引(键值 指针 不存储data 2叶子节点存储键值和所有data记录节点都是按键值的大小顺序存放在同一层的叶子节点并通过指针进行链接
InnoDB B树索引 在MySQL数据库中索引是在存储引擎层实现的这意味着每个引擎的B树索引的实现方式可能是不同的取决于存储引擎实现的本身。 在InnoDB存储引擎中,数据文件本身就是按照B树方式存放数据的。其中B树的键值为主键若在建立时没有显式地指定主键则InnoDB存储引擎会自动创建一个6字节的列作为主键(rowId)。因此在InnoDB存储引擎中可以将B树索引分为聚集索引和辅助索引(非聚集索引)。无论是何种索引每个页的大小都为16KB且不能更改。 聚集索引和辅助索引的区别 聚集索引与辅助索引底层数据结构都是B树区别仅在于所存放数据的内容: 聚集索引是根据主键创建的一棵B树叶子节点存放表中的所有记录。 辅助索引普通索引是根据索引键创建的一棵B树叶子节点仅存放索引键值以及该索引键值指向的主键。 提示如果通过辅助索引来查找数据那么当找到辅助索引的叶子节点后很有可能还需要根据主键值查找聚集索引来得到数据这种查找方式又被称为回表。因为辅助索引不包含行记录的所有数据这就意味着每页可以存放更多的键值因此其高度一般都要小于聚集索引。 回表先通过普通索引扫描出数据所在的行存储的是聚簇索引-主键的值而非数据再通过行主键值去主键聚集索引的叶子节点中去获取完整的数据这样的查询等同于需要多扫描一棵索引树这就是回表, 简单说就是基于非主键索引的查询需要多扫描一棵索引树。
如何避免回表 可通过索引覆盖解决。在索引中包含所有需要获取的所有字段查询结果可以直接全部拿到字段数据不需要通过主键索引再次去获取。
索引结构InnoDB B树
存储单元 磁盘最小单元是扇区一个扇区的大小是 512个字节 文件系统最小单元是块一个块的大小是 4K InnoDB存储引擎最小单元称之为页数据页Page)一个页的大小是16KMySQL的InnoDB存储引擎以Data Page数据页作为磁盘和内存之间交互的基本单位。 B树存储结构 mysql数据库中table表中的表数据(记录)都是存储在页中是以页的形式存放的页在磁盘中不一定是连续, 且页是分布在表空间文件.ibd文件内,例如 user 用户表表空间文件 数据页结构图 说明
B树存放的数据量
B树的存储总记录数 根节点指针数 * 单个叶子节点记录条数假设一条的记录大小为1KB单个叶子节点记录条数数据页16KB/1KB 16条 假设主键ID为bigint类型长度为8字节而指针大小为6字节共14字节。 则一个页中可存放组合(即指针)即 1024 * 16 / 14 1170可以算出一棵高度为2的B树能存放 1170 * 16 1.87万3阶的B树能存放 1170 * 1170 * 16 2200万 数据记录。
