如果1>a>b>0,那么计算结果大于1是算数是在一元二次方程中△什么时候大于零?

一、“2=4”考虑下面这个方程:x^{x^{x^{x^{...}}}} = 2 \;\; (x>0) 它的独特之处在于两点:(1) 等号左边是“指数套指数”的运算,它有个名字——迭代幂次(Tetration),不过为了叙述起来更形象,暂且叫它“指数塔”好了;(2) 省略号表明指数塔是无穷阶的。而且指数塔的运算次序是从上而下的,意味着a^{b^{c}} = a^{\left( b^c \right)} \neq {\left( a^b \right)}^c 回到之前的方程上,它看似无从下手,但是无穷阶与自上而下运算相结合,可以带来一种异常巧妙的解法——把塔底的 x 单独拿出来,剩余的部分恰好是原来的指数塔(无穷的便利),也就等于 2 ,因此解得 x=\sqrt{2} :x^{\color{red}{\left( x^{x^{x^{...}}} \right)} } = 2 \quad \Rightarrow \quad x^{\color{red}{2} } = 2 \quad \Rightarrow \quad x=\sqrt{2} 当然,等号右边的 2 没有任何特殊之处,完全可以用其他的数替代:x^{\color{blue}{\left( x^{x^{x^{...}}} \right)} } = \color{blue}{N} \quad \Rightarrow \quad x^{\color{blue}{N} } = \color{blue}{N} \quad \Rightarrow \quad x=\color{blue}{N^{1/N}} 解法简单直观,可以轻松理解,一切都是如此和谐美好,直到有人把 N=4 代入了上面的式子:x^{\color{blue}{\left( x^{x^{x^{...}}} \right)} } = \color{blue}{4} \quad \Rightarrow \quad x^{\color{blue}{4} } = \color{blue}{4} \quad \Rightarrow \quad x=\color{blue}{\sqrt[4]{4}} = \sqrt{2} 不论是 N=2 ,还是 N=4 ,都有 x=\sqrt{2} ,把这个解分别带回原来的两个方程,可以得到:2 = {\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{...}}}} = 4 简单来说: 2=4 这显然是错误的,那么问题出在哪里?二、“无穷阶指数塔”像这样的悖论通常有两个套路:(1) 偷偷地让等号两边同时除以 0 ;(2) 解完方程后不验根,直接把解带回原方程,然后假装这个式子成立。“ 2=4 ”就属于后者——x=\sqrt{2} 可能是某个方程的增根,但是整个过程中并未检验,最终导致了上面的荒谬结果。要想完成验根,就必须理解“无穷阶指数塔”这个独特的运算,从而计算{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{...}}}} = \; ? \quad (*) 首先,我们丢掉“无穷”的限制,先看有限层的指数塔。既然层数有限,那就可以从顶端自上而下依次计算。比如一个五层的指数塔,每层都是 2 ,计算结果是一个 19729 位数:2^{2^{2^{2^{2}}}} = 2^{2^{2^{4}}} = 2^{2^{16}} =
2^{65536} \approx 2 \times10 ^{19728} 仅仅五层就达到上万位,可见它的增长速度远超指数级别,这也是很多人认为 (*) 式右边是 +\infty 的原因:无穷多个 \sqrt{2} 相乘是无穷大,叠成指数塔之后应该增长得更快。不过别急着下定论,先看看“无穷阶”如何理解。包含无穷多次的运算有不少,除了无穷级数和无穷乘积之外,分数和根式也能无限嵌套,形成无穷连分数与无穷根式:1 + \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{8} + \cdots = 2 \dfrac{2}{1} \cdot \dfrac{2}{3} \cdot \dfrac{4}{3} \cdot \dfrac{4}{5} \cdot \dfrac{6}{5} \cdot \cdots = \dfrac{\pi}{2} 1+\cfrac{1}{1 + \cfrac{1}{1 + \cdots}} = \dfrac{\sqrt{5}+1}{2} \sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}} = 2 关于上面这些运算的处理,思路就是“由有限推无限”。以第一个无穷级数为例,我们取前 n 项进行加和,得到部分和 S_n ,如果部分和数列 \{S_n\} 的极限存在,即 S = \lim_{n \to \infty} {S_n} ,那么 S 就称为无穷级数的和。无穷级数的计算对于分数和根式来说,它们的运算自下而上或自里向外,取部分项的策略稍有变化,但是整体思路大致不变:通过舍弃后面无限的部分,得到一个近似结果的数列,再取极限,结果就是无穷连分数与无穷根式的值。Brilliant Wiki上介绍了这类运算的一般定义和收敛性质,感兴趣的朋友可以前去查看。无穷连分数的计算将这个定义方式应用到无穷阶指数塔上:取指数塔最底层的 n 阶,计算结果 T_n ,然后计算数列 \{ T_n\} 的极限 \lim_{n \to \infty} {T_n} ,如果极限存在,它就是指数塔的值;如果极限不存在,那么指数塔的值也不存在。比如下面这个指数塔,由于它的奇数阶 \{ T_{2m+1}\} 收敛到 0.658365599\dots ,偶数阶 \{ T_{2m}\} 收敛到 0.690347126\dots ,所以 \{ T_n\} 极限不存在,因此原指数塔没有值。无穷阶指数塔的计算三、再看“2=4”知道了无穷阶指数塔的计算方法,我们回头再看 (*) 式。它的结果就是如下数列的极限(如果极限存在的话):\left\{ \sqrt{2} ,\, {\sqrt{2}}^{\sqrt{2}} ,\, {\sqrt{2}}^{{\sqrt{2}}^{\sqrt{2}}} ,\,
{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{\sqrt{2}}}} ,\, \cdots \right\} 可以发现,这个数列(记为 \{T_n\} )能够通过指数函数 f(x)=\sqrt{2}^x 得到:首项 T_1 = \sqrt{2} ,迭代关系为 T_{n+1} = \sqrt{2}^{T_n} 。我们关注的数列极限 T=\lim_{n \to \infty} T_n 可以通过以下三步求出,这里只介绍大体思路:(1)
\sqrt{2} \leq T_n < 2 ,即 \{T_n\} 有界,可用数学归纳法证明;(2)
\{T_n\} 单调递增,可结合 \{T_n\} 的上下界证明;(3) 由单调有界定理可知 \{T_n\} 收敛,即 T 存在。根据迭代关系,可以列出关于数列极限的方程 T=\sqrt{2}^T ,解得 T=2 或 4 。但是 T_n < 2 ,所以 4 为增根,应当舍去,最终得到 (*) 式的结果:{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{...}}}} = \; 2 回头再看“ 2=4 ”悖论,其中的错误就很明显了。对于下面的方程来说x^{x^{x^{x^{...}}}} = N 当 N=2 时,方程有解 x=\sqrt{2} ;当 N=4 时,通过检验发现,我们之前解出的 x=\sqrt{2} 是增根,实际上方程无解。所以将解代回原方程时,只能得到下面的关系:2 = {\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{{\sqrt{2}}^{...}}}} \neq 4 这就解决了“ 2=4 ”悖论。按理说,这个问题到此已经结束了,但是它又引出了一个有趣的谜团:当 N 取什么值时,方程有解?或者换个角度,当 x 取什么值时,这个指数塔才有意义?四、再看“无穷阶指数塔”假设一个指数塔完全由常数 a\,(>0) 构成:a^{a^{a^{a^{...}}}} 它的结果就是下面这个数列的极限(如果存在的话):\left\{ a ,\, {a}^{a} ,\, {a}^{{a}^{a}} ,\,
{a}^{{a}^{{a}^{a}}} ,\, \cdots \right\} 上一节中,我们通过找数列前后项之间的关系,解决了 a=\sqrt{2} 的情形。这里使用类似的处理方法,即迭代关系来自指数函数 f(x)=a^x 。由于迭代的起点为 a ,自然会随 a 取值的不同而变化,但是因为 a^1=a 恒成立,我们可以把迭代起点固定为 1 ,而且不改变数列的极限:\left\{ \color{red}{1} ,\, a ,\, {a}^{a} ,\, {a}^{{a}^{a}} ,\,
{a}^{{a}^{{a}^{a}}} ,\, \cdots \right\} 数列的首项为 T_0 = 1 ,迭代关系为 T_{n+1} = a^{T_n} 。既然说到了函数迭代,就要用上最直观的二维图像工具:蛛网图(cobweb plot)。简单来说,蛛网图就是二维坐标系内由一系列横线和竖线交替构成的折线,它的绘制过程离不开两个函数:用于迭代的函数 y=f(x) 与 y=x ,前者自然是参与迭代,后者则是将迭代的结果再传递给自变量,为下一次迭代做准备。绘制蛛网图的步骤大致如下:(1)根据函数迭代的起点 c ,确定蛛网图的起点为 (c,0) ,从这个点开始绘制蛛网图;(2)做一次函数迭代——如果蛛网图此时所在的点为 (p,q) ,那么它下一个经过的点就是 (p, f(p)) 。这相当于经过当前的点画一条竖直的线,并找到它与函数 y=f(x) 的交点;(3)将迭代的结果再赋给自变量——如果蛛网图此时所在的点为 (p,q) ,那么它下一个经过的点就是 (q,q) 。这相当于经过当前的点画一条水平的线,并找到它与函数 y=x 的交点;(4)重复以上两步,直到迭代结果满足我们的需求。例如,我们希望从 c 开始迭代 2 次,那么蛛网图的起点就是 (c,0) ,并且折线经过的点依次为:(c,0) \to (c,f(c)) \to (f(c),f(c)) \to (f(c),\color{red}{f(f(c))}) 下面是一张动图,简单展示了蛛网图的绘制方法:蛛网图的绘制对于指数塔来说,参与迭代的函数就是 f(x)=a^x ,迭代起点为 (1,0) ,而且指数塔是无穷阶的,意味着我们关注的不是折线上的某个点,而是折线最终收敛到哪个点。接下来就看看指数塔的值与蛛网图随 a 的变化情况,图中的绿点代表蛛网图收敛到的点:指数塔的值与蛛网图随a的变化可以发现,在 a 变化的过程中,蛛网图出现了三种不同的形式:(1) 当 a 足够大时,蛛网图会一直向上延伸,呈现“爆炸”的趋势;(2) 当 a 足够小时,蛛网图呈现螺旋形,在两个不同的数值之间交替跳动;(3) 当 a “大小适中”时,蛛网图最终会收敛到一个点。对于(1)和(2),由于数列 \left\{ 1 ,\, a ,\, {a}^{a} ,\, {a}^{{a}^{a}} ,\, \cdots \right\} 的极限不存在,所以指数塔的值也不存在。只有在(3)的情况下,上述数列的极限存在,指数塔的值才可以确定。那么这三种情况的分界点在哪里呢?a=1 时,以上数列显然收敛,就不再细说了。接下来,我们分别对 f(x)=a^x 单调递增( a>1 )和单调递减( 0<a<1 )的情况进行讨论。1. f(x) 单调递增,即 a>1 时我们之前了解过 a=\sqrt{2} 的情况,这里的情形与之类似:数列 \left\{ 1 ,\, a ,\, {a}^{a} ,\, {a}^{{a}^{a}} ,\, \cdots \right\} 是严格单调递增的,因此它的蛛网图是“阶梯型”的。简单展示一下 a 变化所带来的影响:a&amp;amp;amp;gt;1时的蛛网图从上面的动图可以看出,要确保数列 \left\{ 1 ,\, a ,\, {a}^{a} ,\, {a}^{{a}^{a}} ,\, \cdots \right\} 的极限存在, y=a^x 需要与 y=x 有至少一个交点,这样就可以确定第一个临界情况: y=a^x 与 y=x 恰好相切。a&amp;amp;amp;gt;1时的临界情况假设切点坐标为 (x_0,y_0) ,根据切点满足的方程以及 f(x) 在切点处的斜率为 1 ,可以求解出 a,x_0,y_0 :\begin{cases} y_0 = x_0 \\ y_0 = a^{x_0} \\ a^{x_0}\ln{a} = 1 \end{cases} \Rightarrow \begin{cases} a = e^{1/e} \\ (x_0, y_0) = (e,e) \end{cases} 也就是说,当 1<a \leq e^{1/e} 时,指数塔的值存在,且值域为 \left( 1,e \right] ;当 a>e^{1/e} 时,指数塔的值不存在;二者的临界情况为 a=e^{1/e} ,此时有:\left( e^{1/e} \right)^{\left( e^{1/e} \right)^{\left( e^{1/e} \right)^{\cdots}}} = e 有了“阶梯型”的蛛网图作为直观铺垫,把上面的思想严格化就并不困难了。我们考察的数列 \{ T_n \} 是单调递增且有界的,所以极限存在,然后借助不动点方程求解这个极限,整个过程本质上与 a=\sqrt{2} 的情形无异:(1)
假设 c_a 是方程 a^x=x 的较小的根,则1 \leq T_n < c_a ,可用数学归纳法证明;(2)
\{T_n\} 单调递增,可结合 \{T_n\} 的上下界证明;(3) 求解不动点方程,结合 \{ T_n \} 的上界确定其极限—— \lim_{n\to\infty} T_n = c_a 此处不再展开。2. f(x) 单调递减,即 0<a<1 时这种情况就很有趣了。乍一看, 0<a<1 时, y=a^x 和 y=x 在 (0,1) 上必然有一个交点,从 1 开始迭代的话,蛛网图自然会向内螺旋,收敛似乎是必然的。不过数学总是能给人惊喜:0&amp;amp;amp;lt;a&amp;amp;amp;lt;1时的蛛网图蛛网图有时会收敛到不动点,而其他时候会在不动点周围振荡。中间似乎还有另一个临界情况:0&amp;amp;amp;lt;a&amp;amp;amp;lt;1时的临界情况为什么会这样?回到蛛网图上来。0<a<1 时的蛛网图是“螺旋型”的,和刚刚处理的“阶梯型”相比,它经过的点是在 y=x 两侧交替跳动的,因此缺少单调变化的性质,处理起来比较棘手。不过我们可以尝试把“螺旋型”转化为“阶梯型”,具体做法是将 f(x) 左上的部分沿 y=x “翻折”下来,也就是取 f(x) 的反函数 g(x)=\log_{a}{x} :经过翻折,蛛网图的左上部分和右下部分也会有重叠:去掉这些蛛网图重复经过的部分,剩下的恰好是一个“阶梯型”的图案。不过需要提醒一下,这个图形是夹在 f(x)=a^x 和 g(x)=\log_{a}{x} 之间的,和 y=x 无关,所以并不是蛛网图。翻折后得到的“阶梯型”图案收敛但既然是夹在 f(x) 与 g(x) 之间并且向左上方延伸的“阶梯型”图案,它最终就会收敛到 f(x) 与 g(x) 的一个交点上。确切地说,是收敛到更横坐标靠近 1 的交点上。首先, f(x) 与 g(x) 恰好有一个在 y=x 上的交点。如果它们只有这个交点,就像上图中的情况一样,事情就简单许多。假设这个交点为 (p,p) ,由于翻折后的图形收敛到 (p,p) ,所以原来的蛛网图也会收敛到 (p,p) ,意味着它对应的指数塔等于 p 。但是如果 f(x) 和 g(x) 还有其他的交点呢?假设除了 (p,p) 之外,这两个函数还有一个交点 (r,s) (r \neq s) ,那么就有:由于 f(x),g(x) 定义域和值域的限制,这个交点的坐标介于 0 和 1 之间,也就是 0<r<1 , 0<s<1 ;f(x) 和 g(x) 的图像关于 y=x 对称,所以 (s,r) 也是二者的交点;如果 r>p ,那么 p<r<1 ,此时交点 (r,s) 的横坐标更靠近 1 ;如果 r<p ,由于f(x) 和 g(x) 都是单调递减的,所以有 p<s<1 ,此时交点 (s,r) 的横坐标更靠近 1 。无论是哪种情况,翻折后的图形都不会收敛到 (p,p) 。初看好像没什么大不了的,毕竟翻折后的图形还是收敛了,只是收敛到的点 (r,s) 横纵坐标不同。但是对于原来的蛛网图来说,这可不是好消息,因为在这种情况下,蛛网图会在 (r,s) 和 (s,r) 两点间振荡:翻折后得到的“阶梯型”图案收敛,但原来的蛛网图振荡的情形翻折蛛网图,抵消重复经过的路径,讨论函数交点,实际上就是为了说明一件事:在 0<a<1 的情况下,当 f(x) 和 g(x) 只有一个交点时,蛛网图收敛,指数塔的值存在;有多于一个交点的时候,蛛网图会在两点间振荡,指数塔的值不存在。所以判别指数塔的值是否存在,就相当于判断 f(x)=a^x 和 g(x)=\log_a{x} 的交点个数。至于交点个数,这个答案已经写得很简洁清晰了:我们只从函数图像的角度简单理解一下上面的结果。对于 f(x) 和 g(x) 来说,有两点是可以确定的:f(x) 和 g(x) 必然有一个交点 (p,p) ,即 f(p)=g(p)=p ;x=1 时, f(x) 在 g(x) 上方,即 f(1)>g(1)=0 ;如果能在 x=p 的右邻域内找到一个点 x_0 \in (p, 1) ,使得 f(x_0) < g(x_0) ,结合 f(1)>g(1) ,根据介值定理,我们就可以在 x_0 和 1 之间制造另一个交点。而为了让f(x_0) < g(x_0) 能够成立,我们希望 f(x) 在 x=p 的右邻域内比 g(x) “减小得更快”,也就是 f(x) 和 g(x) 在 x=p 处的导数满足如下关系:f'(p)<g'(p)<0 结合 f(p)=g(p)=p ,解如下不等式,可以得到 a 的取值范围:\begin{cases} a^p = p \\ a^p\ln{a} < \frac{1}{p\ln{a}} <0 \end{cases} \Rightarrow \begin{cases} 0<p<\dfrac{1}{e} \\ 0<a=p^{1/p}<(\frac{1}{e})^e\end{cases} 所以当 0<a<(1/e)^e 时,f(x) 与 g(x) 有三个交点,此时蛛网图振荡。而当 a=(1/e)^e 时, f(x) 与 g(x) 在处的斜率恰好相等,此时只有一个交点,又回归了蛛网图收敛的情况。那么,如何说明 a=(1/e)^e 就是临界情况(2)呢?遗憾的是,我能想到的函数图像直观解释到此为止了。要严格证明 a=(1/e)^e 是一个交点与三个交点的临界情况,需要稍复杂的构造与推导:而且原先的“翻折”操作,本质上是将数列 \{ T_n \} = \left\{ 1 ,\, a ,\, {a}^{a} ,\, {a}^{{a}^{a}} ,\, \cdots \right\} 的奇数项子列 \{ T_{2n+1} \} 与偶数项子列 \{ T_{2n} \} 的极限囊括在一个坐标中考虑。如果两个坐标相同,也就是上文提到的 (p,p) ,那么原数列的极限就是 p ,意味着指数塔的值也是 p ;如果两个坐标不同,也就是上文提到的 (r,s)\,(r \neq s) ,那么两个子列会分别收敛到 r 和 s ,导致原数列的极限不存在,因此指数塔的值也不存在。说明两个子列分别收敛,并且判断二者的极限是否相同,同样需要下功夫构造:上面引用的回答和文章都很详细,这里就不再花篇幅介绍了。总结一下这种情况的内容:当 (1/e)^e \leq a<1 时,指数塔的值存在,且值域为 \left[ 1/e, 1 \right) ;当 0<a<(1/e)^e 时,指数塔的值不存在;二者的临界情况为 a=(1/e)^e ,此时有:\left( 1/e^e \right)^{\left( 1/e^e \right)^{\left( 1/e^e \right)^{\cdots}}} = \frac{1}{e} 最后用一张表整理一下之前的结果:这与我们之前讨论“ 2=4 ”时得到的结果一致: a^{a^{a^{\cdots}}} 的值域为 [1/e, e] , 2 落在值域中,原方程有解;而 4 不在值域中,所以方程是无解的。还有一点值得一提:对于两个临界情况来说,如果对 f(x) 求导,并且将不动点代入,你会发现导数的绝对值都是 1 :a=e^{1/e} 时, f(x) = (e^{1/e})^x \; \Rightarrow \; f'(x) = (e^{1/e})^x/e \; \Rightarrow f'(e)=1 a=(1/e)^e 时,f(x) = (1/e^e)^x \; \Rightarrow \; f'(x)=-e(1/e^e)^x \; \Rightarrow \; f'(1/e)=-1 这正是不动点稳定性的临界情况
f'(x_0)|=1 。了解数值分析的朋友可以尝试一下,使用迭代过程的收敛性判据解决上面的问题。五、有迭代,就有分形再回到最初的指数塔问题,里面似乎还有一个细节:x^2=2 \quad \Rightarrow \quad x=\sqrt{2} 而另一个根 x=-\sqrt{2} 因为题设要求被直接舍去了。你可曾想过,如果真的把 -\sqrt{2} 放进指数塔里,结果会怎样?{(-\sqrt{2})}^{{(-\sqrt{2})}^{{(-\sqrt{2})}^{{(-\sqrt{2})}^{...}}}} = ? 要解答这个问题,我们首先需要知道负数的幂如何计算。而这就要回到复数的两种表示形式上——一种是我们比较常见的 z=x+iy ,另一种则是指数形式 z=re^{i\theta} 。其中 x 为实部, y 为虚部, r(>0) 为模, \theta 为辐角,它们均为实数。两种表达形式的相互转化如下图所示。复数的两种表示形式与相互转化关系其中 z=x+iy 的形式适合做指数运算,例如 e^z = e^{x+iy} = e^xe^{iy} ,结果是一个模为 e^x ,辐角为 y 的复数。而 z=re^{i\theta} 的形式适合做对数运算,例如\ln(z) = \ln(re^{i\theta}) = \ln{r} + \ln{e^{i\theta}} = \ln{r}+ \color{red}{i\theta'} ,结果是一个实部为 \ln{r} ,虚部为 \color{red}{\theta'} 的复数。需要注意的是,一个复数的辐角有无穷多个,它们之间相差 2\pi 的整数倍,所以 z 的对数应该是个多值函数。不过我们这里只取辐角主值,也就是取在区间 (-\pi, \pi] 内的辐角作为结果。了解了复数的指数与对数运算,我们来看看如何计算一个复底数复指数的幂。以 i^i 为例:利用恒等式 a^b = e^{b\ln a} 换底—— i^i = e^{i\ln i} ;计算指数——由于 i 的模为 1 ,辐角主值为 \dfrac{\pi}{2} ,所以 \ln i =\ln(1 \cdot e^{\frac{\pi}{2}i}) = \frac{\pi}{2}i ,因此指数为 i \ln i = i \cdot \dfrac{\pi}{2}i= -\dfrac{\pi}{2} ;计算结果—— i^i=e^{-\frac{\pi}{2}} 复数的幂搞定了,负数的幂自然不在话下,因为负数只是辐角主值为 \pi 的一类复数。以 {(-\sqrt{2})}^{{(-\sqrt{2})}} 为例,用上面的流程走一遍,结果是:{(-\sqrt{2})}^{{(-\sqrt{2})}} = 2^{(-\sqrt{2}/2)} \cos(\sqrt{2}π) - i \cdot 2^{(-\sqrt{2}/2)} \sin(\sqrt{2}π) 好像还是很复杂……但这最起码是一个正常的复数形式。况且,我们目标是了解计算方式,计算的活全部丢给计算机就好了~和之前的情况类似,对于由 -\sqrt{2} 构成的指数塔,我们想知道数列 \left\{ -\sqrt{2}, \, {(-\sqrt{2})}^{{(-\sqrt{2})}}, \, {(-\sqrt{2})}^{{(-\sqrt{2})}^{{(-\sqrt{2})}}}, \dots \right\} 的收敛情况,就可以通过几行代码直接了解它的前 1000 项。可以发现,最终的结果是九个数一循环,所以我们关注的数列并不收敛,意味着 {(-\sqrt{2})}^{{(-\sqrt{2})}^{{(-\sqrt{2})}^{{...}}}} 的值并不存在。要是把其他的数放进指数塔呢?比如虚数单位 i ,结果是收敛的!而且它的收敛过程相当漂亮,如果我们将数列 \{ i, \, i^i, \, i^{i^i}, \, \dots \} 中的数在复平面内标出来,然后用线连接相邻的两项,得到的结果就是这样的:复平面内的数列{i, i^i, i^(i^i), ...}一个缓慢向内收缩的螺旋!至于计算它收敛到哪个点,也就是解一个复数方程的事,就当成作业吧,这里只给出答案:i^{i^{i^{\cdots}}} = 0.4382829 \dots + 0.3605924\dots i看到这里,你估计能猜到这一节标题中的分形是怎么回事了。和曼德勃罗特集(Mandelbrot Set)的构造方法类似,我们考察由函数 f_a(z) = a^z 迭代得到的数列是否有界:\left\{ 1 ,\, a ,\, a^a ,\, a^{a^{a}} ,\, a^{a^{a^{a}}} ,\, \dots \right\} 如果有界,就把复平面内的 a 标黑,否则就按照发散速度的快慢标记其他颜色,最终的结果就是迭代幂次分形(Tetration Fractal)。它画出来是这样的(图片注释中标记了各图的坐标范围):迭代幂次分形:-4<x<4, -4<y<4迭代幂次分形:-0.7<x<-0.3, 0.5<y<0.9迭代幂次分形:-0.26<x<-0.16, -0.20<y<-0.10迭代幂次分形:-0.193<x<-0.183, 0.230<y<0.240又是一个惊艳的分形!迭代幂次分形放大的细节似乎只有两种:(1) 从一头引出多个分支,(2) 螺旋。和曼德勃罗特集相比,它在细节上欠缺一些多样性。但是迭代幂次分形的绘制难度并不小!曼德勃罗特集的收敛域可以确定为
z|<2 ,意味着如果迭代过程中,如果某个点的模超过 2 ,那么这种情况必然发散。但是对于迭代幂次分形来说,这个收敛域会非常大(甚至有可能不存在)!在上面的图中,收敛域均设置为
z|<10^{48} ,即便如此,增大收敛域的范围,还能不断在当前的图中增加细微的变化。说它是一个“永远画不对”的分形,大概也不为过吧。参考资料The strange properties of the infinite power tower - An "investigative math" approach for young students关于指数塔的一次探索。内容详实,介绍了每一种情况的直观理解与严格推导,不动点的稳定性,收敛域外的分支,以及指数塔的历史背景。Exponentials Reiterated从方程 x^y=y^x 引出的指数塔。读起来有些费劲,不过文末的几个和指数塔相关的问题值得一看。The Fractal Boundary of the Power Tower Function看标题就知道它讲的是什么了 :P. 除了分形之外,还介绍了Lambert-W函数与指数塔的关系。

1 背景
Btree 自 1970 年 Bayer 教授提出后,一直是关系型数据库中核心数据结构,基于多路的分叉树,将数据范围自上而下不断缩小,直到需要的记录,通常在数据库中一个 Btree 结点能展开几百上千个分叉,数据的搜索范围呈指数级下降,极大地减少了数据访存次数,提升搜索效率。对于 B-tree 的基础操作,如插入、删除、更新,以及分裂/合并等操作已有大量的文献介绍,如果需要了解或有所疑问,可以参考文章末尾的参考文献 [3]。在伴随着高并发和需要考虑事务处理的数据库系统下,Btree 索引往往需要考虑更为复杂的场景。本文深入 MySQL Innodb 引擎,介绍 Innodb 中 Btree 的组织形式以及操作数据的具体实现,着重考虑其在高并发访问时,如何保证数据、Btree 结构的一致性,以及如何考虑事务的 ACID 特性。
2 索引组织表 (IOT)
Innodb 是一种行存的存储引擎,一条记录(record)对应于数据表中的一行,包含多个列(field),除了用户自定义的 field 之外,Innodb 还会给每个 record 增加几个隐藏 field:最新修改的事务 ID、用于回滚和 MVCC 构建旧版本的回滚指针、以及未定义主键时的 row ID。这里我们将能唯一识别一条记录的前若干个 field 组合称为 key fields,其余的 field 组合为 value fields。
数据库的核心是高效组织和访问数据,便于用户快速检索和修改数据,MySQL 目前的主流 Innodb 引擎,采用的是索引组织表的形式,顾名思义,将表的数据组织为 B-tree 的形式,如图 1 所示,整个 btree 结构由多个结点组成,每个结点对应于真实物理文件的划分的固定大小的 page,Innodb 中默认是 16 KB。表中所有数据记录(data record,包含 key 和 value)有序存放在 b-tree 的叶子结点中,形成一个递增的 record 列表,非叶子结点存有 child 结点 key 的最小值以及 child 节点的 page 号 (index record,包含 key 和 page no),通过 page 号能从数据库缓存系统(buffer pool)中快速定位到 child 节点,这个包含所有数据的 Btree 也被称为主键索引(或者聚集索引),数据库每创建一张表,默认就是生成了一颗主键索引 btree。
对于二级索引,会生成一颗新的 btree,使用主键索引 value 中的某些 field 作为新的 btree 的 key,主键索引的 key 作为新的 btree 的 value,先从二级索引定位到主键索引的 key,再回主键索引拿到完整的记录,避免当以主键索引的 value 作为搜索条件时进行全表扫描的开销,提高搜索效率。
图 1: Innodb 的索引组织表形式
3 索引页和行结构
在 Innodb 中,对于任何数据的查询和修改,最终都是落在磁盘物理文件的访问操作中。简单来说,是通过 btree 定位到具体的物理 page,对 page 内部的 record 进行增删改查。Btree Page 内部本身可以看作一个有序的 record 单向链表,通过一些元信息对 16 KB 的物理空间进行高效管理和组织。每个 Page 中存在两个特殊的 record:infimum record 和 supremum record,分别代表 page 中 record 的无穷小和无穷大,位于 record 链表的头和尾。如图 2 所示,在 record 链表上,每间隔几个 record 会选取一个 record 作为 directory slot,这样查找时先二分搜索定位到具体的 slot,在 slot 进一步线性搜索定位到具体的 record。默认初始时,存在两个 directory slot,分别指向 infimum 和 supremum,随着 page 中 record 不断插入和删除,directory slot 的数目也会动态变化。
图 2: direction slot
Innodb Btree 中无论是叶子结点,还是非叶子结点,都有着相同 page 和 record 格式,图 3 给出了 Innodb 中索引 page 和 record 的物理格式(page_t 和 rec_t),对于 page 可以分为四个部分:page 本身的元信息、用于 btree 和 record 组织的索引元信息、record 空间和 directory slot 空间。
Page Header 和 Page Tail:包含 page 的元信息,如最新修改全局的日志序号(LSN)信息、维护同一层 Btree 的 page 的相邻 page 号,以及 page 的校验 checksum 信息等。
Index Header:这块是索引 page 的元信息,包含 page 内 directory slot 的数目,目前还未分配给 record 使用的空间偏移(Heap top),目前已经分配的 rec 数目(包含有效或者被回收的 rec),用于复用的 Free record List (最后被删除的 record 的偏移),page 内部有效的 record 数目(n_recs),以及当前 page 在 Btree 中的层级 (level,Btree 的叶子结点是第 0 层)。
record 空间:从 94 byte 往后就是 innodb page 存放 record 的区域,依此存放 infimum、supremum,用户 record 集合,以及还未分配的空间。
directory 空间:存放 directory slot 数组以及其指向的 record,所有 directory slot 是逆序存放的。
record 空间中存的就是上层用户写入的一行行记录 (rec_t),Innodb 中有两种行格式,Compact 和 Redundant 格式,MySQL 5.1 之后默认提供 Compact 格式了,本文也主要介绍 Compact 格式的 record。Record 主要分为两部分:Header 部分和 data 数据部分。
Header 元信息,在代码中以 Extra data 形容:首先是变长列的长度数组,这是按列的顺序存储的。第二部分存了行中为 NULL 的记录的 bitmap,这个 bitmap 的大小由索引元信息中最多允许多少个 NULL 的记录决定。后面多个字段决定当前 record 的状态,delete mark 标记当前 record 是否被删除(Innodb 中用户删除 record 都是标记删除,真正物理删除是由后台 purge 线程触发,保证没有其他用户并发访问时执行)。Min rec flag 标记当前 record 是否是非叶子层的最小值,使得搜索小于 btree 所有行时,能够定位在最小的叶子结点上。N_owned 是用于作为 directory slot 指向的 record 使用,说明了当前 directory slot 包含的 record 数目,用于判断是否需要分裂或者收缩 directory slot。Page 中整个 record 空间是一个堆,每分配一个新的 Record,都会分配一个 heap no,这个 heap no 在事务系统中也用于唯一确定 page 内部 一个行锁对象。Status 标识了当前 record 状态:data record(ORDINARY)/ index record(NODE_PTR)/ INFIMUM / SUPREMUM。Next 指向 record 链中下一 record 在 page 内部的偏移。
data 数据部分:这是用户数据真正存储的位置,首先是 key fields,用于 record 的比较,唯一确定一个 record 在 Btree 的位置。Trx ID 和 Roll ptr 分别是最新修改的事务 ID 以及用于回滚和 MVCC 构建版本的回滚指针。后面的 Value fields 则是非 key 的列数据。
图 3: Innodb 的索引页和行结构
4 cursor 搜索
用户通过 SQL 下发操作的指令和要操纵的数据,通过 MySQL server 层的解析,在传入 innodb 引擎层时,会将需要操作的记录转换成 InnoDB 内存的记录格式(dtuple),以及表中具体行的增、删、改、查操作。dtuple 格式的内容比较直接,和 rec_t 中的数据部分是一致的,在操作时临时分配创建的。要操作一个表的数据,首先要通过 dtuple 中的 key fields 和逻辑上 btree 定位到数据存储的物理位置 (rec_t),这在 innodb 通过 cursor 搜索来实现的,每次 open 一个 cursor 都会开启一个从 btree root 结点搜索到指定层级的 record 的搜索过程。在搜索时指定搜索模式(search_mode),并发控制的加锁模式(latch_mode) 以及 搜索过程的行为(flag)。Innodb 中 search mode 是考虑到在 page 内部进行二分查找时定位在哪个 record,考虑到不同 record 的查找需求,有以下 4 种。:
PAGE_CUR_G: > 查询,查询第一个大于 dtuple 的 rec_t
PAGE_CUR_GE: >=,> 查询,查询第一个大于等于 dtuple 的 rec_t
PAGE_CUR_L:
PAGE_CUR_LE:
插入操作的 search_mode 默认是 PAGE_CUR_LE,即插在最后一个小于等于该 dtuple 的 rec_t 后。
图 4: Cursor 定位流程
cursor 搜索整个核心操作在 btr_cur_search_to_nth_level 中。这个函数较为复杂,省去 AHI 和 spatial index 以及下一节介绍的并发控制逻辑,主要流程是:
从 dict_index_t 元信息中拿到 root page 在物理文件的 page no(默认是 4)。
从 buffer_pool 中根据 page no 拿 page(buf_page_get_gen),buffer pool 模块会根据 page 是否被缓存来决定是从内存中还是磁盘中读取,并根据加锁策略对 page 加锁。
对 page 内部的 record list 进行二分搜索 (page_cur_search_with_match),Innodb 的二分搜索是在图 2 中 directory slot 指向 record 进行的,先定位到相邻的两个 slot,在两个 slot 范围内进行线性搜索将 dtuple 与 rec_t 逐个进行比较,确定小于和大于等于 dtuple 的相邻 rec_t(low_rec 和 up_rec),并将 low_rec 和 up_rec 匹配的 fields 数记录下来(low_match 和 up_match),最后根据 search_mode 进行选取 rec_t。
如果没有到达指定 level,当前一定会是非叶子结点,会从 rec_t 提取 child page 所在的 page_no,重走步骤 2,直到到达指定 level.
在 cursor 搜索过程中,会根据上层指定的 flag,触发 cursor 搜索过程的行为,主要分为几种类型:
insert buf 相关,包括 BTR_INSERT、BTR_DELETE_MARK、BTR_DELETE 等,在二级索引回表时指定,如果主键索引叶子结点不在内存中,缓存相应操作,按一定频率合并写入主键索引的 page 中,避免频繁的随机 IO 开销。
lock intention 相关,包括 BTR_LATCH_FOR_INSERT、BTR_LATCH_FOR_DELETE,正常 innodb 在搜索到 leaf page 时,会把上层的锁都放了,而这两种类型在某些场景需要保留上层锁,如对于 insert,如果因当前 page 满了要插入到右 page 的第一个 record,会触发上层的 delete。对于 delete,如果删除 page 第一个 record,会触发上层 page 的 insert。
BTR_ESTIMATE:在 range scan 时会估计 range 范围内的 record,此时会保留 cursor 搜索路径的所有 page 信息,用于估计计算。
BTR_MODIFY_EXTERNAL:当处理 Blob 字段类型涉及到外部 page 时需要特殊处理[5],对整个 index 会加 sx 锁。
cursor 搜索的结果在 Innodb 是可以复用,持久化为 persist cursor(pcur),避免未修改时的重复搜索开销,这块内容我们将在 select 篇继续介绍。
5 并发控制
对于一个需要支持大量并发业务的实时事务处理 OLTP 系统而言,并发控制策略成了数据库 btree 实现的关键,在多线程并发搜索、查询、修改过程中,保持 Btree 结构的一致性。Innodb 中对于 btree page 的操作都被包含在一个 mini-transaction(mtr)中,用户线程操作 btree 前开启一个 mtr,在操作 btree 过程中,将访问的 page 指针、请求的锁 latch、以及产生的 redo log 分别挂在 mtr 上,当操作流程结束提交 mtr 时,将 redo log 同步到全局 log buffer 中,将脏页加入 flush list 上,最后释放所有持有的 latch。真正修改只有在 mtr commit 提交,redo 落盘才生效,因此 mtr 的实现将上层对记录的操作可以看作一个对 btree 的原子操作,也是 cursor 搜索并发控制的基本单位。
图 5: lifecycle of mini-transaction (mtr)
Innodb 对于 btree 修改的保证还是基于锁 latch 实现的,访问任何一个 page 内容都需要持有其 latch,读加 S 锁,写加 X 锁。除此之外,还有一种 SX 锁类型,与 S 锁兼容,与其他 SX 和 X 锁互斥,独占写权限但允许读。同时为了保证因 page 满或者稀疏而分裂或合并引起 btree 结构发生变化时的正确性,Innodb 还有一把整个 index 的全局 latch,在 dict_index_t 元信息中。
Btree 是树状组织的数据结构,在访问加 latch 需要满足一定顺序,才能防止死锁。然而保证加锁顺序的同时,还需要尽可能减少 latch 持有的范围,提高访问并发度。Innodb 经过多年的发展,在 btree latch 上的也做了大量的优化。文章 [4] 对于 innodb btree latch 的发展做了全面的概述,本文不再展开叙述,主要介绍在 MySQL 8.0 版本 btree latch 的机制。整体上遵守自顶向下,自左向右的访问策略,因此如果要访问一个 page 的 上层 page 或者 左边(prev)page,都需要从 root 结点开始重新遍历搜索。
对于读操作(BTR_SEARCH_LEAF),不会引起 btree 结构发生变化,对 index latch 加 S 锁,一路顺着 cursor 搜索路径,沿路对 page 加 S 锁,直到达 leaf page。
对于修改操作时,分为两种情况,认为当前修改不影响 btree 结构的乐观修改(BTR_MODIFY_LEAF)、以及认为当前修改会使得 btree 结构发生变化的悲观修改(BTR_MODIFY_TREE),两种搜索加锁策略的粒度是不同的,如图 6 所示。
乐观修改和读操作类似,会对 index latch 加 S 锁,一路顺着 cursor 搜索路径,沿路对 page 加 S 锁,到 leaf page 加 X 锁进行修改即可。
悲观修改加锁更为复杂,首先对 index latch 加 SX 锁,即此时仅允许一个悲观修改访问 btree,但允许并发的读操作和乐观修改。顺着 cursor 搜索路径,初始时不对沿路 page 加锁(此时其他访问不可能修改非叶子 page),当访问到 leaf page 的 parent 时,会对进行两层判断,如果修改会及联修改 parent 的父结点以上,这时到达 leaf page 时会将沿路的 page 重新加上 X 锁,如果 btree 的修改仅限于 parent,这时仅将 parent 的锁加上。当到达 leaf page 时,会将 leaf page 及其前后的 page 都加上 latch (需要修改前后 page 的指向)。
对于悲观修改,会递归修改上层 page(BTR_CONT_MODIFY_TREE),因为第一次悲观修改已经加好锁,再次搜索是无需对 page 加锁。
在 Innodb 中,某些场景需要获取某个 dtuple 的前一个 page (BTR_SEARCH_PREV 和 BTR_MODIFY_PREV),例如向前 range scan 需要跨 page 到前一个 record 时。由于加锁顺序问题,无法在持有当前 page 的 latch 拿去 previous page 的 latch,因此需要从 btree root 重新遍历,在持有 previous page 的 parent 的 latch 的情况下,释放当前 page 的 latch,获取 previous 的 page 的 latch。这里遍历加锁时候,还要特殊处理 previous page 和 当前 page 不在同一个 parent 的情况。
图 6: 乐观修改加锁路径(左)、悲观修改加锁路径(右)
6 Insert 路径解析
介绍完 Innodb 中 Btree 组织形式、搜索和并发控制策略,我们此时来看 Innodb 中 btree 是如何插入一条数据的。Innodb 在插入时需要对主键索引和二级索引分开考虑,先插入主键索引,再插入二级索引。
整个插入流程函数在 row_ins 中,插入前会先判断主键索引是否 unique(即是否定义主键),不是则会先分配 row id 来唯一标识一条 record。
无论主键索引还是二级索引,都需要先构建插入的完整行记录的内存版本(row,dtuple type),再基于 row 和各个索引(dict_index_t)的列信息构建真正需要插入索引中存储的版本(entry,dtuple type),进行 cursor 搜索定位到最后一个小于等于该 dtuple 的 rec_t 后,从 page 内部申请空间插入 entry 的内容。
6.1 主键索引的 insert 路径
主键索引的插入流程在 row_ins_clust_index_entry 函数中,先进行加锁范围更小的乐观插入流程,如果插入失败(page 空间不足),会进行悲观插入流程,加锁范围更大,并触发结点分裂流程,这也和 cursor 的乐观悲观搜索相对应。
控制乐观和悲观插入流程在 row_ins_clust_index_entry_low 中,根据 latch_mode 进行判断,每次都开启一个新的 mtr 流程,我们先看乐观插入:
先进行乐观 cursor 搜索(BTR_MODIFY_LEAF),定位到 leaf page 的 rec_t 中。
duplicate check: 检查定位的 rec_t 是否和要插入的 entry 相等,存在重复,会将可能相等的 record 都加上事务锁(普通 insert 加 S lock,insert on duplicate key update 则加 X lock,gap mode 取决于事务隔离级别),保证不被其他事务修改。如果 rec_t 不是 delete mark,向上层返回 duplicate key 错误,如果是 delete mark,将插入流程转为 update-in-place 覆盖写入(row_ins_clust_index_entry_by_modify)。
否则进入乐观插入(btr_cur_optimistic_insert),首先会计算插入 entry 空间,先判断 page 中 free list 空间是否足够,free list 空间不够,再判断 page 中未分配的堆的空间,如果还是不够,会判断 reorganize page 后的空间(整理 page 内部的空间碎片),如果存在空闲空间,将 entry 内容 copy 到申请的 rec_t 中,并更新 rec_t 和 page 的元信息,否则会进行悲观插入。
真正插入 entry 前,会检查事务锁和记录 undo(btr_cur_ins_lock_and_undo),检查事务锁 (lock_rec_insert_check_and_lock) 会判断 cursor 定位的下一个 rec_t 上当前有没有锁,有的话加上带有 gap 的插入意向的 X 锁(LOCK_X
LOCK_GAP
LOCK_INSERT_INTENTION )的显示锁,来等待其他 gap 锁释放,确保要插入的区间没有其他事务访问。同时每一条 Insert 的 rec_t 上都默认有一个隐式锁,它是通过 trx_id 和当前活跃事务数组的 id 来检测的,这么做减少了 lock_sys 的操作,提升性能[6]。为了保证事务回滚,插入 entry 前会记录一条 insert 类型的 undo(trx_undo_report_row_operation),将 entry 的 key fields 写入 undo page 中,便于回滚时找到 record 的位置,并根据 undo page 的 id 和 offset 构建出回滚指针存入插入的 rec_t 中[7]。
在写入 entry 之后,会向 mtr 的 log buf 记录 redo log (page_cur_insert_rec_write_log),用于 WAL 故障恢复,通常一条 insert 的 redo log 会记录 page 和 index 信息,以及和 cursor 定位的 rec_t 相比的差异部分(btree的有序特性,相邻的 record 相同部分较多,减少存储的 redo log 大小):
(Page ID, offset) + (len of each field) + (extra info) + (bytes which differs from cursor record)
6.2 结点分裂
如果 cursor 搜索到的 leaf page 剩余空间不足以容纳待插入的 entry,会触发悲观插入流程,腾出插入的空间:
先进行悲观的 cursor 搜索流程,将涉及的 page 的 latch 都加上。
检查事务锁和记录 undo。
进行结点分裂,最后将 entry 插入到分裂后的 page 中,写 redo。
整个结点分裂过程在 btr_page_split_and_insert 中,如图 7 所示,主要是:
选择原 page 的分裂点 (split_rec)。
生成新 page,将原 page 的部分 record list 批量 move 到新 page 中,这里会写 move 相关的 redo(包括原 page 的 delete 和新 page 的 insert)。
修改前后 page 的指针指向、在 parent page 新增一个 index record 指向新 page(触发新的插入流程)。
根据 entry 和 split_rec 的大小关系,将 entry 插入到原 page 或者新 page 中的一个。
图 7: 结点分裂流程
原 page 的分裂点的选择,为了性能考虑,Innodb 采用了两种策略[8]:
将原始页面中 50% 数据移动到新页面,这是最普通的分裂方法。
为了优化上述中间点分裂在顺序插入场景的问题,InnoDB 实现了在插入点分裂的方法,在每个 page 上记录上次插入位置 (PAGE_LAST_INSERT),以此判断本次插入是否递增或者递减,如果判定为顺序插入,就在当前插入点进行分裂。
6.3 二级索引的 insert 路径
前面介绍二级索引由主键索引的部分 value fields 作为 sk(secondary key),主键索引的 pk (primary key) 作为 value。二级索引的插入流程整体和主键索引相差不大,可以参考主键索引流程,但存在以下几个区别:
duplicate check:二级索引 unique 性质是由 sk 决定的,而和主键索引不同,二级索引覆盖一个 delete mark 的 rec_t,需要满足所有 fields 都相等(sk + pk),因此对于一个 unique 的二级索引,可能存在多个被 delete-mark 的相同 sk 不同 pk 的 rec_t,并且跨多个 page。在搜索时,为了保证 unique 性质,需要把所有被 delete-mark 的 rec_t 以及第一个 sk 不相同的 rec_t 都加上 next-key 锁(gap 锁加在下一个 rec),阻止其他事务插入相同的 sk 的 record 造成 unique 不一致。
由于插入都是以 PAGE_CUR_LE 模式插入,所以插入时候搜索会定位到最后一个相等 sk 的 rec_t 上,然而由于相等 rec_t 可能跨 page,为了符合加锁顺序,在 duplicate check 的时候,会把上一个 mtr 提交,开启一个以 PAGE_CUR_GE 模式的 cursor 搜索过程来加 gap 锁。
由于 gap 锁加了第一个与 sk 不相同的 rec_t,当这中间的 gap 很大时,会造成即使在 RC 隔离级别下,也会很容易发生死锁问题,也是官方遗留很多年的问题,这在文章 [9] 有很好的例子、解释以及方案讨论,感兴趣的可以仔细阅读。
二级索引不需要通过记录 undo 来支持事务回滚和 MVCC 一致性读。
7 总结
本文介绍了以下几个方面:btree 的背景、Innodb 中 btree 的组织形式,包括索引组织表逻辑形式以及 btree 索引页和记录的物理格式。接下来介绍了从 Innodb 中定位 record 的方法和如何保证 btree 的一致性,包括了 cursor 搜索逻辑和并发控制流程。最后介绍了 Innodb 整个 insert 路径,以及如何考虑其他模块如 事务锁、undo、redo、BP 等。btree 索引是数据库的核心,是直接操纵数据的模块,通过 btree 来看 Innodb,对整个数据库都会有更深层次的理解。审核编辑:刘清
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。
举报投诉

我要回帖

更多关于 在一元二次方程中△什么时候大于零 的文章