什么是随机查找？为什么说b树b+树支持随即查找

Question

如题，随机查找从何种角度理解“随机”这一个词语？b树b+树不也是从上到下层层查找吗？为什么就是随机的呢？随即查找的定义是什么呢？

Answer 1

一年过去了，考研已经结束了，由于这个问题下面一直有消息，现在趁着研0的闲暇，再来看一看这个问题。
首先说说顺序查找，对于一个数组，顺序查找，从数组的第一个开始，要查找到值为val的元素，查找的顺序为1，2，3，4，5，...，n。无论val是多少，查找的顺序都是按照1-n的顺序，只是停止查找的位置不一样而已。
再来看随机查找，比如b树，对树的每一个结点编号。假设按照层次遍历的顺序进行编号，从root开始查找，假设root的编号是m，那么对于带查找的值val，如果val是任意可能的值，那么查找序列是...，你会发现除了能够确定第一个查找编号是m以外，无法确定下一个查找的编号。因此呢，这个查找的编号序列是随机的，和val有关系。对比顺序查找，无论val是什么，只要没有查找到成功或者失败的结点，那么查找序列总是1，2，3， ...
有些人会觉得说，如果val是知道的，那么查找路径就是确定的呀，哪里是随机的，不也是从上到下按顺序查找的吗。但是如果你认真看了上述两段话的对比，你就可以发现，这不是区别所在。顺序查找是，无论什么情况，查找都是顺序的；随机查找是，除非精确到某一次具体的查找，否则你永远无法确定查找的序列。
以上的感悟都来自于维基百科，我的感受不一定正确，所以我直接附上维基百科上的解释，需要的同学可以自行理解。
Random search
From Wikipedia, the free encyclopedia
Jump to navigationJump to search
Random search (RS) is a family of numerical optimization methods that do not require the gradient of the problem to be optimized, and RS can hence be used on functions that are not continuous or differentiable. Such optimization methods are also known as direct-search, derivative-free, or black-box methods.
Anderson in 1953 reviewed the progress of methods in finding maximum or minimum of problems using a series of guesses distributed with a certain order or pattern in the parameter searching space, e.g. a confounded design with exponentially distributed spacings/steps.[1] This search goes on sequentially on each parameter and refines iteratively on the best guesses from the last sequence. The pattern can be a grid (factorial) search of all parameters, a sequential search on each parameter, or a combination of both. The method was developed to screen the experimental conditions in chemical reactions by a number of scientists listed in Anderson's paper. A MATLAB code reproducing the sequential procedure for the general non-linear regression of an example mathematical model can be found here (FitNGuess @ GitHub).[2]
The name "random search" is attributed to Rastrigin[3] who made an early presentation of RS along with basic mathematical analysis. RS works by iteratively moving to better positions in the search space, which are sampled from a hypersphere surrounding the current position.
The algorithm described herein is a type of local random search, where every iteration is dependent on the prior iteration's candidate solution. There are alternative random search methods that sample from the entirety of the search space (for example pure random search or uniform global random search), but these are not described in this article.
Random search has been used in artificial neural network for hyper-parameter optimization.

来自 https://en.wikipedia.org/wiki/Random_search