二叉树
由n（n0）个有限节点组成一个具有层次关系的集合，看起来就像一个倒挂的树，因此称这样的数据结构为树。一个节点的子节点个数叫做度，通俗的讲就是树叉的个数。树中最大的度叫做树的度，也叫做阶。一个2阶树最多有2个子节点即最多有2叉，因此这样的树称为二叉树，二叉树是树家族中最简单的树。两个叉的树就是二叉树，可这除了用来按一定结构存放数据外，跟查询性能好像也没关系，不会又是一个没用的噱头吧。二分查找
听说二叉树的原始威力来源于一种叫做二分查找的算法。相传在鹦鹉的原始社会，存在着森严的等级制度，每只鸟必须按高矮顺序分出等级和尊卑。那么问题来了，如下图，怎样才能找出最高、最矮、中等高的那些鹦鹉呢、以及指定高度的那只呢?第一种方法:扫描法一个一个依次测量，完毕后所有的问题都迎刃而解。这种一个一个依次全部测量的方法叫做扫描，他的缺点很明显，最高和最矮，需要全部测量完毕才能知晓。而对于指定高度，最好的情况是第一次就找到；最坏的情况是最后一次才找到，时间复杂度为n，也就是说从13个鹦鹉中找到指定身高的那只，最坏的情况是查13次。第二种方法：二分法13个鹦鹉全部听令，按从矮到高列队，向左看齐，报数。报数字1的就是最矮的，报数字13的就是最高的，报数字7的就是中等身高的那只。最好和最坏的情况都是一次找到。而查询性能一下子提高13倍，我的个乖乖，无论多个只鹦鹉，时间复杂度都是1，好可怕。问题：我不服，你这是偷换概念，有本事对比一个查找指定高度鹦鹉的性能。因为鹦鹉们已经按高矮排好了队，所以指定高度的鹦鹉，要么是站中间那个只，要么就是在它的左边或右边的那群里。如果是中间那个，一次就找到，如果不是只需要从中间左边或右边那一半中找，再在这一半中找中间那只，对比身高。以此类推，每次都把查询的范围减半，时间复杂度log2(n)。那么log2(13)就是4，最坏的情况也才4次，时间复杂度确实不是1了，但好像也不糟，简化如下：问题：如果按高矮排队，仍然需要一个一个比较，跟扫描有什么区别，那还不如直接扫描呢？事实确实如此,单纯的一次查询，先排序，再二分查找，不见得比扫描快，甚至还不如。但是，在数据的世界，大部分数据一生会被查询无数次，如果只在数据降生的时候排一次序，往后余生，是不是就可以直接用二分查找，这似乎就是传说的读多写少，以及对应的复用。优点：查找快
缺点:必须有序，需要提前排序
每次查找都需要不断计算中间位置
二分查找树
如果一组数据不会或不常变更，那么他们的位置也基本不变。可是每次查询都需要重新计算中间位置是一种浪费，而浪费可耻。我们能不能把所有中间节点组织起来，每次使用时，直接取中间节点?请看下图，找到所有单次二分查找的中间节点，把他们连起来，并用手提起最中间的那个节点，就是一棵二分查找树。优点：二分查找树就是通过数据结构的方式实现了二分查找算法，通过存储中间节点的数据，弥补了二分查找每次都要计算中间位置的缺点。平衡二叉树:
如果二分查找树不断进行修改，比如删除某些节点，经过一段时间后，最早那个中间节点的数据（根），很可能就不在中间了。中间位置就像一个天平的支点，如果他不在中间了，那么整个天平就会失衡，失衡的世界就会坍塌成不伦不类的瘸树，甚至是降维成一个链表或者数组。二分查找算法的关键在于有序和中间节点，而二分查找树的关键是中间节点的维护，如果维护的节点已经不在中间了，那么它就失去了意义。所以必须保证「二分查找树」是一个正确的树，一个根节点在中心的树，一个左右子树层级（高度）基本相等（高度相差不超过1）的树，一个平衡的树。平衡二叉树中最常见的就是红黑树：红黑树规定了一系列节点颜色规则，以及对应的左旋和右旋操作来保证颜色规则，从而达到树的平衡性。看到这花里胡哨的颜色以及复杂的规则，让人第一眼就望而却步，但所有的这些，也不过是为了保证二叉树的平衡性，由于维持平衡的操作太过麻烦，无法用一句话简单概括，只好用一堆人*难分的规则和步骤来实现，只要按着这些步骤就一定能实现二叉树的平衡。平衡二叉树=二分查找树+平衡（左右高度相差不超过1）平衡二叉树并未提高二分查找树的性能，它只是保正树不会被二向箔（多次增删改）打击降维成链表或不对称的残缺树，永远维持平衡。另外，不仅仅是二叉树，其他种类的树，也是需要有序和平衡，才能发挥最大的威力。多叉树之B-te
两个叉的树就能折半查询，理论可以提高一倍性能，那么多个叉是不是能提高更多倍性能？如下图的3阶（叉）树（所有数据仅用于演示，非真实分布）每个节点维护两个数据，并指向最多3个子节点。如图3个子节点的数据分别为：小于17，17~35，大于35。假设，从上图中查找10这个数，步骤如下：找到根节点，对比10与17和35的大小，发现在左子节点，也就是第2层节点；
从根节点的指针，找到左子节点，对比10与8和12的大小，发现，数据在当前节点的中间子节点，也就是第3层节点；
通过上步节点的指针，找到中间子节点（第3层节点），对比10与9和10的大小，发现==10，因此找到当前节点的第二数即为结果。
加上忽略的12个数据，从26个数据中查找一个数字10，仅仅用了log3(26)≈3次，而如果用平衡二叉树,则需要log2(26)≈5次，事实证明，多叉树确实可以再次提高查找性能。多叉树是在二分查找树的基础上，增加单个节点的数据存储数量，同时增加了树的子节点数，一次计算可以把查找范围缩小更多。优点：二叉平衡树的基础上，使加载一次节点，可以加载更多路径数据，同时把查询范围缩减到更小。复杂节点:至此，我们列举的数据都是孤零零的单个数字。试想，你手里已经有一个数据10，为什么还要费力吧唧的再从一堆数据中找到这个10，自己找自己？这不是有病吗？单个数字只能活在演示中，现实的世界要复杂的多，我们来看一个接近真实场景的案例。现有一个以年龄为索引的3阶树，存储了一批用户信息，如下图：数字为用户的年龄，其它为与树排序查找无关的业务数据，像这种索引数据与树排序查找无关的业务一起维护在节点的平衡多叉（阶）树称为B-树（B树）。缺点：业务数据的大小可能远远超过了索引数据的大小，每次为了查找对比计算，需要把数据加载到内存以及CPU高速缓存中时，都要把索引数据和无关的业务数据全部查出来。本来一次就可以把所有索引数据加载进来，现在却要多次才能加载完。如果所对比的节点不是所查的数据，那么这些加载进内存的业务数据就毫无用处，全部抛弃。磁盘I/O
计算机的功能主要为：计算、存储和网络。而用于计算的数据以及计算后的结果很大一部分都需要存储起来，以备后续再次使用。向磁盘中存储和读取的过程叫磁盘I/O。磁盘的读取方式和速度会严重影响到整个业务的计算性能。下面我们简单了解一下磁盘是如何工作的。磁盘大概长这个样子：磁盘主要由磁盘盘片、传动手臂、读写磁头和马达组成。为了存储容量,主轴像穿糖葫芦一样把多个磁盘片组成一个阵列。通过马达驱动主轴转动以及传动手臂移动，使读写磁头在磁盘片上读写数据。大概如下：磁盘片由很多半径不等的同心圆组成，这些圆被称为磁道，数据就是写在这些磁道上。每个磁道又划分成块称为扇区。如果磁盘是一记事本，那么一张磁盘片就是本子的一页纸，而主轴就是本子的装订线；磁道就是纸页的行，而扇区可以看作是很宽的列。如果在磁盘中存储一首诗,想象中大概这个样子。磁盘的读I/O操作,需要找到数据所在的磁盘片，以及对应的磁道和扇区。这些操作类似于从一本书中找到数据所在的页，行，列。因为每个磁盘片都对应一个磁头，所以性能的关键就在于找行和列，即寻道和磁盘旋转。寻道即通过磁头找到数据所在的磁道，相当于换行到数据所在行。由于磁头只能水平移动，即只能换行寻道，无法在指定磁道上移动，因此需要磁盘高速旋转移动到指定扇区，类似写春联时，笔不动，纸动。综上所述，磁盘的读写是通过机械运动来定位数据所在位置，而cpu是通过电信号进行数字运算。粗略的认为，机械查询数据，与光速处理数据的性能完全不是在一个量级，总之一句话就是磁盘处理太慢太慢了。虽然磁盘处理数据太慢了，但是它是目前相对廉价且稳定的存储设备，所以又不能舍弃不用，但大致可以通过以下方法进行优化。尽量减少I/O次数，比如可以使用缓存；
每次I/O尽量获取更多的数据；
每次I/O尽量获取有用的数据，当然相应的也间接减少总I/O次数；
多叉树之B+te
做为数据库的索引，无论用什么样的数据结构维护，这些数据最终都会存储到磁盘中。鉴于磁盘I/O的性能问题，以及每次I/O获取数据量上限所限，提高索引本身I/O的方法最好是，减少I/O次数和每次获取有用的数据。B-te已经大大改进了树家族的性能，它把多个数据集中存储在一个节点中，本身就可能减少了I/O次数或者寻道次数。但是仍然有一个致命的缺陷，那就是它的索引数据与业务绑定在一块，而业务数据的大小很有可能远远超过了索引数据，这会大大减小一次I/O有用数据的获取，间接的增加I/O次数去获取有用的索引数据。因为业务数据才是我们查询最终的目的，但是它又是在「二分」查找中途过程无用的数据，因此，如果只把业务数据存储在最终查询到的那个节点是不是就可以了？理想很丰满，现实很骨瘦如柴，谁知道哪个节点就是最终要查询的节点呢？B+te横空出世，B+树就是为了拆分索引数据与业务数据的平衡多叉树。B+树中，非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据。这样即保证了叶子节点的简约干净，数据量大大减小，又保证了最终能查到对应的业务数。既提高了单次I/O数据的有效性，又减少了I/O次数，还实现了业务。但是，在数据中索引与数据是分离的，不像示例那样的？如图：我们只需要把真实的业务数据，换成数据所在地址就可以了，此时，业务数据所在的地址在B+树中充当业务数据。总结
数据存储在磁盘（SSD跟CPU性能也不在一个量级），而磁盘处理数据很慢；
提高磁盘性能主要通过减少I/O次数，以及单次I/O有效数据量；
索引通过多阶（一个节点保存多个数据，指向多个子节点）使树的结构更矮胖，从而减少I/O次数；
索引通过B+树，把业务数据与索引数据分离，来提高单次I/O有效数据量，从而减少I/O次数；
索引通过树数据的有序和「二分查找」（多阶树可以假设为多分查找），大大缩小查询范围；
索引针对的是单个字段或部分字段，数据量本身比一条记录的数据量要少的多，这样即使通过扫描的方式查询索引也比扫描数据库表本身快的多；
知识扩展
树的结构最大的优点就是查询性能高，因此所有需要提高查询性能的都可以考虑树。而现实中也确实有这样的例子，比如：HashMap中的数据冲突时，链表转化成红黑树；
数据库索引使用的B+树；
搜索引擎倒排索引使用的字典树；
以上只是浅尝辄止、点到为止的描述了数据库使用B+树索引为什么能提高查询性能原因及简单过程。并没有深入各种数据结构的细节，也未提及其它索引类型和索引的具体存储格式，目的仅仅是，为了让大家对索引有一个感性的认识。DTCC中国数据库技术大会PPT下载新鲜出炉！阿里彻底拆中台了！如何打造一个经常宕机的业务系统？MySQL高频面试题，都在这了放弃腾讯75W年薪，回老家当公务员，提离职被领导教育，网友：leader嫉妒了王垠：怎样尊重一个程序员？年薪30万+的程序员，都是这样谈薪资的...年11月DB-Engines排行：Oracle归零年内涨幅PostgSQL增长第一独秀中国程序员VS印度程序员，太有味了...快手回应厕所装坑位计时器，这届打工人：再也不能愉快地带薪拉屎了？伟大耀眼，C语言发展史的点点滴滴中国程序员VS美国程序员，这也太形象了吧...
你「在看」吗？预览时标签不可点收录于话题#个上一篇下一篇