天道酬勤,学无止境

btree

JAVA面试核心知识点(二):数据库

二·数据库 2.1 数据库架构 考点思维导视 关系数据库:架构、索引、锁、语法、理论范式 如何设计一个关系性数据库:RDBMS 程序实例 存储管理,缓存机制,SQL解析,日志管理(beanLog),权限划分,容灾机制,索引管理,锁模块 存储(文件系统) 索引模块 为什么要使用索引 快速查询数据 什么样的信息能成为索引 主键、唯一键以及普通键 索引的数据结构 生成索引,建立二叉查找树进行二分查找 生成索引,建立B-Tree结构进行查找 生成索引,建立B+-Tree结构进行查找 生成索引,建立Hash结构进行查找 理论范式: 第一范式:数据库列具有原子性,不可再分割 第二范式:属性完全依赖于主键 第三范式:数据库表中不能含有另外一张表的非主属性字段 2.2 优化你的索引 二叉查找树 :二分查找法 查询效率 O(logn) 可能会成为线性导致查询效率降低为O(logn) B-Tree 平衡多路查找树O(logn) 定义: 根节点至少包括两个孩子 树中每个节点最多包含m个孩子(m>=2) 除根节点和叶节点外,其他每个节点至少有ceil(m/2)个孩子 所有叶子节点都位于同一层 假设每个非终端节点包含有n个关键字信息,其中 a)Ki(i=1..n)为关键字,且关键字按顺序升序排序K(i-1)<>Ki b)关键字得个数n必须满足:[ceil(m/2)-1]<=n<=m-1 c)非叶子节点得指针

2021-03-27 02:00:51    分类:博客    mysql   innodb   myisam   btree