二叉搜索树的查找 递归算法_二叉树的高度

阿里面试：分析为什么B+树更适合作为索引的结构以及索引原理 　　mysql的B+树索引 查找使用了二分查找，redis 跳表也使用了二分查找法，kafka查询消息日志也使用了二分查找法，二分查找法时间复杂度O(logn); 　　在MySQL中，主要有四种类型的索引，分别为：B-Tree索引，Hash索引，Fulltext索引(MyISAM 表)和R-Tree索引，本文讲的是B-Tree索引。 　　后面的索引原理一定要看，太重要了，阿里两个人都问这个mysql的索引原理 　　mysql使用了 B+索引：B树：有序数组+平衡多叉树；B+树：有序数组链表+平衡多叉树； 　　一、Mysql索引主要有两种结构：B+Tree索引和Hash索引 　　(a) Inodb存储引擎 默认是 B+Tree索引 　　(b) MyISAM 存储引擎 默认是Fulltext索引； 　　(c)Memory 存储引擎 默认 Hash索引； 　　Hash索引 　　mysql中，只有Memory(Memory表只存在内存中，断电会消失，适用于临时表)存储引擎显示支持Hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B+Tree索引。 　　Hash索引把数据以hash形式组织起来，因此当查找某一条记录的时候，速度非常快。但是因为hash结构，每个键只对应一个值，而且是散列的方式分布。所以它并不支持范围查找和排序等功能。 　　B+Tree索引 　　B+Tree是mysql使用最频繁的一个索引数据结构，是Inodb和Myisam存储引擎模式的索引类型。相对Hash索引，B+Tree在查找单条记录的速度比不上Hash索引，但是因为更适合排序等操作，所以它更受欢迎。毕竟不可能只对数据库进行单条记录的操作。 　　带顺序访问指针的B+Tree 　　B+Tree所有索引数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都有指向相邻叶子节点的指针。 　　这样做是为了提高区间效率，例如查询key为从18到49的所有数据记录，当找到18后，只要顺着节点和指针顺序遍历就可以以此向访问到所有数据节点，极大提高了区间查询效率。 　　大大减少磁盘I/O读取 　　数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点需要一次I/O就可以完全载入。 　　什么是索引 　　索引（Index）是帮助数据库高效数据的数据结构。索引是在基于数据库表创建的，它包含一个表中某些列的值以及记录对应的地址，并且把这些值存储在一个数据结构中。最常见的就是使用哈希表、B+树作为索引。 　　一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。 　　为什么要使用索引 　　我们知道，数据库查询是数据库最主要的功能之一。而查询速度当然是越快越好。而当数据量越来越大的时候，查询花费的时间会随之增长。而索引，可以加速数据的查询。因为索引是有序排列的。 　　举个例子来说，假设我们有一个数据库表Employee，这个表分别有三个字段：name，age，address。假设表中有1000条记录。 　　假如没有使用索引，当我们查询名为“Jesus”的雇员的时候，即调用： 　　此时数据库不得不在Employee表中对这1000条记录一条一条的进行判断name字段是否为“Jesus”。这也就是所谓的全表扫描。 　　而当我们在Employee表上的name字段上创建索引时，当我们查询名为“Jesus”的雇员时，会通过索引查找去查询名为“Jesus”的雇员，因为该索引已经按照字母顺序排列，因此要查找名为“Jesus”的记录时会快很多，因为名字首字母为“J”的雇员都是排列在一起的。通过该索引，能到表中对应的记录。 　　举例说明使用索引的好处 　　假设索引（索引是一种数据结构）是链表结构。每个节点存储的是关键字字段（这个例子中对应的是name属性）以及该关键字字段在数据库表的对应的记录的地址。而这些节点是根据name属性排序的（即根据字母顺序排序）。 　　因此，当我们执行上面说的查找名为“Jesus”的sql语句时，数据库会通过该索引来查询，因为该链表是有序排列的，在我们找到第一个name属性为“Jesus”的节点后，继续往后找，当遇到name属性不为“Jesus”的节点时，就无需再往后查找了，因为节点是根据name属性有序排列的啊。假设第一个name=“Jesus”的节点是第499个节点，最后一个name=“Jesus”的节点是第500个节点，那么只需要遍历501个节点就可以了。当发现第501个节点的name字段不为“Jesus”，后面的499个节点也就无需遍历了。 　　通过索引，我们就找到了name为“Jesus”的节点，而通过该节点的另一个属性（关键字字段在数据库表的对应的记录的地址），我们就能到Employee表中满足条件name=“Jesus”的记录了。 　　通过使用索引，查询判断的次数就从1000次缩小到了501次了。起到了加速了查询效率。但实际上数据库中索引的结构，并不是链表结构。 　　数据库中使用什么数据结构作为索引 　　数据库中实际使用的索引并不会是链表结构，因为效率太低了。 　　我们知道链表的查询效率是O(n)。就像上面的例子，遍历了501次才找到第一条符合条件的记录，这是很低效的。而我们知道，数组+二分查找的效率是O(lgn)，但是数组的插入素以及删除素的效率很低，因此使用数组做为索引结构并不合适。 　　另外，在选择数据库索引的结构的时候，要考虑到另一个问题。索引是存在于磁盘中，当索引非常大的时候，达到几个G的时候，无法一次加载到内存中。 　　考虑到上面两个因素，数据库中索引使用的是树形结构。 　　各种树的名字 　　有这么几种树： 　　首先要明白三种树名中的“-”起到的是分隔的作用，并不是“减”的意思。 　　因此正确的翻译应该是B树，B+树，B树。而不是B-树，B+树，B树。因此，当你听到别人说“B减树”的时候，要明白它指的是B-Tree。即B树和B-树是同一种树。 　　为什么要强调上面这一点呢，因为有的博文中写的是：B树是二叉树，B-树是多路搜索树。 　　然而B树和B-树都是指B-Tree。引用维基百科上的话： B-tree Not to be confused with Binary tree. 　　也就是说，B-Tree并不是Binart tree。B-Tree的中文名是平衡多路搜索树。（B树的相关介绍在下面） 　　平衡二叉树 　　树形结构是计算机系统里最重要的数据结构。 　　我们知道，二叉树的查找的时间复杂度是O(log2N)，其查找效率与深度有关，而普通的二叉树可能由于内部节点排列问题退化成链表，这样查找效率就会很低。因此平衡二叉树是更好的选择，因为它保持平衡，即通过旋转调整结构保持最小的深度。其查找的时间复杂度也是O(log2N)。 　　但实际上，数据库中索引的结构也并非AVL树或更优秀的红黑树，尽管它的查询的时间复杂度很低。 　　为什么平衡二叉树也不适合作为索引 　　之前说了平衡树的查找时间复杂度是O(log2N)，已经很不错了，但还是不适合作为索引结构。那么肯定是有一种更适合作为索引的数据结构。 　　那么这个更适合作为索引的数据结构，难道是查找的时间复杂度更低吗？并不是。这种作为索引的数据结构的查找的时间复杂度也近似O(log2N)。 　　那为什么平衡二叉树不适合作为索引呢？ 　　索引是存在于索引文件中，是存在于磁盘中的。因为索引通常是很大的，因此无法一次将全部索引加载到内存当中，因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别。 注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。 　　而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。 　　B-Tree适合作为索引 　　平衡二叉树不适合作为索引。那么什么才适合作为索引——B树。 　　平衡二叉树没能充分利用磁盘预读功能，而B树是为了充分利用磁盘预读功能来而创建的一种数据结构，也就是说B树就是为了作为索引才被发明出来的的。 　　来看看关于“局部性原理与磁盘预读”的知识： 　　局部性原理与磁盘预读： 　　由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。 　　搞清楚上面的意思。磁盘预读是具体实现，其理论依据是局部性原理。 　　为什么说红黑树没能充分利用磁盘预读功能，引用一篇博文的一段话： 红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。 　　也就是说，使用红黑树（平衡二叉树）结构的话，每次磁盘预读中的很多数据是用不上的数据。因此，它没能利用好磁盘预读的提供的数据。然后又由于深度大（较B树而言），所以进行的磁盘IO操作更多。 　　B树的每个节点可以存储多个关键字，它将节点大小设置为磁盘页的大小，充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字，树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少，更多的是在内存中对读取进来的数据进行查找。 　　B树的查询，主要发生在内存中，而平衡二叉树的查询，则是发生在磁盘读取中。因此，虽然B树查询查询的次数不比平衡二叉树的次数少，但是相比起磁盘IO速度，内存中比较的耗时就可以忽略不计了。因此，B树更适合作为索引。 　　比B树更适合作为索引的结构——B+树 　　比B树更适合作为索引的结构是B+树。MySQL中也是使用B+树作为索引。它是B树的变种，因此是基于B树来改进的。为什么B+树会比B树更加优秀呢？B树：有序数组+平衡多叉树；B+树：有序数组链表+平衡多叉树； 　　B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。 　　引用一段话： 走进搜索引擎的作者梁斌老师针对B树、B+树给出了他的意见（为了真实性，特引用其原话，未作任何改动）：“B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。 　　比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。 　　B树比如你的例子中查，17的话，一把就得到结果了， 　　有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。 　　另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。” 　　举个例子来对比。 　　B树： 　　比如说，我们要查找关键字范围在3到7的关键字，在找到第一个符合条件的数字3后，访问完第一个关键字所在的块后，得遍历这个B树，下一个块，直到遇到一个不符合条件的关键字。遍历的过程是比较复杂的。 　　B+树(叶节点保存数据，其他的节点 全部存放索引): 　　相比之下，B+树的基于范围的查询简洁很多。由于叶子节点有指向下一个叶子节点的指针，因此从块1到块2的访问，通过块1指向块2的指针即可。从块2到块3也是通过一个指针即可。 　　引用一篇博文中网友评论的一段话： 数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。 B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。 　　正如上面所说，在数据库中基于范围的查询是非常频繁的，因此MySQL最终选择的索引结构是B+树而不是B树。 　　二、索引的原理 　　一 索引原理 　　索引的目的在于提高查询效率，与我们查阅图书所用的目录是一个道理：先定位到章，然后定位到该章下的一个小节，然后找到页数。相似的例子还有：查字典，查火车车次，飞机航班等 　　本质都是：通过不断地缩小想要数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。 　　数据库也是一样，但显然要复杂的多，因为不仅面临着等值查询，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)等等。数据库应该选择怎么样的方式来应对所有的问题呢？我们回想字典的例子，能不能把数据分成段，然后分段查询呢？ 　　最简单的如果1000条数据，1到100分成第一段，101到200分成第二段，201到300分成第三段……这样查第250条数据，只要找第三段就可以了，一下子去除了90%的无效数据。但如果是1千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是lgN，具有不错的查询性能。 　　但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的。而数据库实现比较复杂，一方面数据是保存在磁盘上的，另外一方面为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。 　　二 磁盘IO与预读 　　考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。 　　每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。 　　三、索引的数据结构 　　任何一种数据结构都不是凭空产生的，一定会有它的背景和使用场景，我们现在总结一下，我们需要这种数据结构能够做些什么，其实很简单，那就是：每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。 　　那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢？就这样，b+树应运而生。 　　

　　如上图，是一颗b+树，关于b+树的定义可以参见B+树，这里只说一些重点，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。 　　真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。 　　b+树的查找过程 　　如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。 　　真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。 　　b+树性质 　　1.索引字段要尽量的小 　　通过上面的分析，我们知道IO次数取决于b+数的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小； 　　而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。 　　这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。 　　2.索引的最左匹配特性（即从左往右匹配） 　　当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据； 　　但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。 　　比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。 　　这也是经常考察的，比如 我定义了 A,B,C的联合索引，如果 我只传递了 A,B 能走索引吗？答案是能，因为最左侧原理(百度问过) 　　补充一下. 全文索引（FULLTEXT）=mysql的 myISAM搜索引擎默认的索引类型 　　MySQL从3.23.23版开始支持全文索引和全文检索，fulltext索引仅可用于 MyISAM 表；他们可以从CHAR、VARCHAR或TEXT列中作为CREATE TABLE语句的一部分被创建，或是随后使用ALTER TABLE 或CREATE INDEX被添加。 　　对于较大的数据集，将你的资料输入一个没有FULLTEXT索引的表中，然后创建索引，其速度比把资料输入现有FULLTEXT索引的速度更为快。不过切记对于大容量的数据表，生成全文索引是一个非常消耗时间非常消耗硬盘空间的做法。 　　文本字段上的普通索引只能加快对出现在字段内容最前面的字符串(也就是字段内容开头的字符)进行检索操作。如果字段里存放的是由几个、甚至是多个单词构成的较大段文字，普通索引就没什么作用了。这种检索往往以LIKE %word%的形式出现，这对MySQL来说很复杂，如果需要处理的数据量很大，响应时间就会很长。 　　这类场合正是全文索引(full-text index)可以大显身手的地方。在生成这种类型的索引时，MySQL将把在文本中出现的所有单词创建为一份清单，查询操作将根据这份清单去检索有关的数据记录。全文索引即可以随数据表一同创建，也可以等日后有必要时再使用下面这条命令添加： 　　有了全文索引，就可以用SELECT查询命令去检索那些包含着一个或多个给定单词的数据记录了。下面是这类查询命令的基本语法： 　　上面这条命令将把column1和column2字段里有word1、word2和word3的数据记录全部查询出来。 　　四、索引使用注意事项 　　1，不要滥用索引 　　①，索引提高查询速度，却会降低更新表的速度，因为更新表时，mysql不仅要更新数据，保存数据，还要更新索引，保存索引 　　②，索引会占用磁盘空间 　　2，索引不会包含含有NULL值的列 　　复合索引只要有一列含有NULL值,那么这一列对于此符合索引就是无效的，因此我们在设计数据库设计时不要让字段的默认值为NULL。 　　3，MySQL查询只是用一个索引 　　如果where字句中使用了索引的话，那么order by中的列是不会使用索引的 　　4，like 　　like ‘%aaa%’不会使用索引而like “aaa%”可以使用索引 　　五、选择索引的数据类型 　　Mysql支持很多数据类型，选择合适的数据类型存储数据对性能有很大的影响。 　　(1)越小的数据类型通常更好：越小的数据类型通常在磁盘、内存和cpu缓存中都需要更少的空间，处理起来更快。 　　(2)简单的数据类型更好：整形数据比起字符，处理开销更小，因为字符串的比较更复杂。在MySQL中，应用内置的日期和时间数据类型，而不是字符串来存储时间；以及用整形数据存储IP地址。 　　(3)尽量避免NULL：应该制定列为NOT NULL，除非你想存储NULL。在MySQL中，含有空值的列很难进行查询优化，因为他们使得索引、索引的统计信息以及比较运算更加复杂。 　　六、MySQL常见索引有：主键索引、唯一索引、普通索引、全文索引、组合索引 　　1，INDEX（普通索引）： 　　最基本的索引，没有任何限制 　　2，UNIQUE（唯一索引）： 　　与“普通索引”类似，不同的就是：索引列的值必须唯一，但允许有空值。 　　3，PRIMARY KEY（主键索引）： 　　是一种特殊的唯一索引，不允许有空值。 　　4，FULLTEXT（全文索引）： 　　仅可用于MyISAM和InoDB，针对较大的数据，生成全文索引很耗时耗空间 　　组合索引： 　　为了更多的提高mysql效率可建立组合索引，遵循“最左前缀”原则。创建复合索引应该将最常用（频率）做限制条件的列放在最左边，一次递减。 　　组合索引最左字段用in是可以用到索引的。相当于建立了col1,col1col2,col1col2col3三个索引 　　参考 　　http://blog.codinglabs.org/articles/theory-of-mysql-index.htmlhttp://blog.csdn.net/v_JULY_v/article/details/6530142http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.htmlhttps://blog.csdn.net/weixin_30531261/article/details/79312676https://www.cnblogs.com/bypp/p/7755307.html 来源：https://www.cxyxiaowu.com/18067.html 作者：aspirant 　　我 @Java编程宇宙，学习更多 Java 知识100 道 Java 面试题汇总 PDF 下载（含答案解析和思维导图）