层次遍历是从上到下,从左到右遍历的方式
深度遍历的三种遍历顺序(左节点一定在右节点前面):
只有给定中序才能将左、右子树分开
# 反推demo
# 前:0,1,3,7,8,4,9,2,5,6
# 中:7,3,8,1,9,4,0,5,2,6
根左右
规则确定第一个是根节点为07,3,8,1,9,4 + 0 + 5,2,6
0+1,3,7,8,4,9+2,5,6
;左子树:1,3,7,8,4,9
;右子树:2,5,6
1,3,7,8,4,9
,左根节点是12,5,6
,右根节点是27,3,8 + (1) + 9,4 + (0) + 5 + (2) + 6
7,3,8 + (1) + 9,4
中根据中序的左根右
规则,7,3,8是左子树,9,4为右子树 左根右
规则,依次对应:左7根3右8
;94中9是左子树,根是45 + (2) + 6
,5是左节点,6是右节点索引是加速
MySQL
对表中数据行的高效获取而创建的一种分散存储的数据结构,正确地创建合适的索引作用是提高数据查询性能的基础。
B+树查询时间,树的高度有关
mysql
默认存储引擎innodb
只显式支持B-Tree( 从技术上来说是B+Tree)索引。 对于频繁访问的表,innodb
会透明建立自适应hash索引,即在B树索引基础上建立hash索引,可以显著提高查找效率,对于客户端是透明的,不可控制的,隐式的。
基于哈希表实现。存储引擎会对所有的列计算一个哈希码, Hash索引将所有的哈希码存储在索引中,同时在索引表中保存指向每个数据行的指针
B树是一种多路搜索树,每个节点可以拥有多于两个子节点。M路的B树最多拥有M个子节点。 B+树中的B代表平衡(balance),而不是二叉(binary),因为B+树是从最早的平衡二叉树演化而来的。