Skip to content

Latest commit

 

History

History
197 lines (117 loc) · 27.5 KB

第二章技术要点.md

File metadata and controls

197 lines (117 loc) · 27.5 KB

第二章 C#要点技术

编译过程

  1. Mono

    graph LR
Start-->C#-->IL-->Mono-->CLR-->JIT-->原生代码-->End;
CLR-->AOT-->原生代码
    Loading

  2. IL2CPP

    graph LR
Start-->C#--借助Mono-->IL-->IL2CPP-->CPP虚拟机-->JIT-->原生代码-->End;
CPP虚拟机-->AOT-->原生代码
    Loading

List 剖析

  1. List是一个C#中最常见的可伸缩数组组件，我们常常用它来替代数组，因为它是可伸缩的，所以我们在写的时候不用手动去分配数组的大小。甚至有时我们也会拿它当链表使用。那么到底它的底层是怎么编写的呢，每次增加和减少以及赋值，内部是怎么执行和运作的呢？我们接下来就来详细的讲解。

  2. List内部是用数组实现的，而不是链表，并且当没有给予指定容量时，初始的容量为0。

  3. List组件在Add,Remove两个函数调用时都采用的是“从原数组拷贝生成到新数组”的方式工作的。

    每次容量不够的时候，整个数组的容量都会扩充一倍，容量的默认值为4。因此整个扩充的路线为4，8，16，32，64，128，256，512，1024…依次类推。

    List使用数组形式作为底层数据结构，好处是使用索引方式提取元素很快，但在扩容的时候就会很糟糕，每次new数组都会造成内存垃圾，这给垃圾回收GC带来了很多负担。

    这里按2指数扩容的方式，可以为GC减轻负担，但是如果当数组连续被替换掉也还是会造成GC的不小负担，特别是代码中List频繁使用的Add时。另外，如果数量不得当也会浪费大量内存空间，比如当元素数量为 520 时，List 就会扩容到1024个元素，如果不使用剩余的504个空间单位，就造成了大部分的内存空间的浪费。具体该怎么做才是最佳的策略，我们将在后面的文章中讨论。

    元素删除的原理其实就是用 Array. Copy 对数组进行覆盖。

  4. Insert 接口与Add接口一样，先检查容量是否足够，不足则扩容。从源码中获悉，Insert插入元素时，使用的用拷贝数组的形式，将数组里的指定元素后面的元素向后移动一个位置。

  5. []的实现，直接使用了数组的索引方式获取元素。

  6. Clear接口在调用时并不会删除数组，而只是将数组中的元素清零，并设置 _size 为 0 而已，用于虚拟地表明当前容量为0。

  7. Contains 接口使用的是线性查找方式比较元素，对数组进行迭代，比较每个元素与参数的实例是否一致，如果一致则返回true，全部比较结束还没有找到，则认为查找失败。

  8. ToArray接口中，重新new了一个指定大小的数组，再将本身数组上的内容考别到新数组上，再返回出来。

  9. Find接口使用的同样是线性查找，对每个元素都进行了比较，复杂度为O(n)。

  10. Enumerator 这个结构，每次获取迭代器时，Enumerator 每次都是被new出来，如果大量使用迭代器的话，比如foreach就会造成大量的垃圾对象，这也是为什么我们常常告诫程序员们，尽量不要用foreach，因为 List 的 foreach 会增加有新的 Enumerator 实例，最后由GC垃圾回收掉。

  11. Sort 排序接口使用了 Array. Sort接口进行排序，其中Array. Sort的源码我们也把它找出来。Array.Sort 使用的是快速排序方式进行排序，从而我们明白了 List 的 Sort 排序的效率为O(nlogn)。

  12. List 并不是高效的组件，真实情况是，他比数组的效率还要差的多，他只是个兼容性比较强得组件而已，好用，但效率差。线程也并不安全，需要加锁机制来保证线程的安全性。

Dictionary 剖析

  1. Hash哈希冲突的方法中通常有：开放定址法、再哈希法、链地址法、建立一个公共溢出区等。Dictionary使用的解决冲突方法是拉链法，又称链地址法。

  2. 拉链法的原理：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为n，则可将散列表定义为一个由n个头指针组成的指针数 组T[0..n-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。

    拉链法结构图

  3. Dictionary 是以数组为底层数据结构的类。当我们实例化 new Dictionary() 后，内部的数组是0个数组的状态。与 List 组件一样，Dictionary 也是需要扩容的，会随着元素数量的增加而不断扩容。具体我们来看看下面的接口源码剖析。

  4. Add接口的实现。Add 接口就是 Insert 的代理，首先在加入数据前需要对数据结构进行构造，首次定义size为3，每次扩大2倍，也就是，3->7->17->37->…. 底层数据结构的大小是按照这个数值顺序来扩展的，除非你在创建 Dictionary 时，先定义了他的初始大小，指定的初始大小也会先被 GetPrime 计算该分配的数量最终得到应该分配的数组大小。这和 List 组件的分配方式一模一样。

  5. Remove部分。删除的过程和插入的过程比较相似，因为要查找到Key元素所在位置，所以再次将Key值做哈希操作也是难免的，然后类似沿着拉链法的模式寻找与关键字匹配的元素。Remove 接口相对 Add 接口简单的多，同样用哈希函数 comparer.GetHashCode 再除余后得到范围内的地址索引，再做余操作确定地址落在数组范围内，从哈希索引地址开始，查找冲突的元素的Key是否与需要移除的Key值相同，相同则进行移除操作并退出。注意源码中，Remove 的移除操作并没有对内存进行删减，而只是将其单元格置空，这是位了减少了内存的频繁操作。

  6. ContainsKey 是一个查找Key位置的过程。它调用了 FindEntry 函数，FindEntry 查找Key值位置的方法跟我们前面提到的相同。从用Key值得到的哈希值地址开始查找，查看所有冲突链表中，是否有与Key值相同的值，找到即刻返回该索引地址。

  7. TryGetValue 尝试获取值的接口与 ContainsKey 同样，他调用的也是FindEntry的接口，来获取Key对应的Value值。

  8. 对[]操作符的重定义在重新定义[]符号的代码中，获取元素时也同样使用 FindEntry 函数，而 Set 设置元素时则使用与 Add 调用相同的 Insert函数，它们都是同一套方法，即哈希拉链冲突解决方案。

  9. 从源码剖析来看，哈希冲突的拉链法贯穿了整个底层数据结构。因此哈希函数是关键了，哈希函数的好坏直接决定了效率高低。

  10. Dictionary 同List一样并不是线程安全的组件，Hashtable在多线程读写中是线程安全的，而 Dictionary 不是。如果要在多个线程中共享Dictionaray的读写操作，就要自己写lock以保证线程安全。

  11. 到这里我们已经全面了解了 Dictionary 的内部构造和运作机制。他是由数组构成，并且由哈希函数完成地址构建，由拉链法冲突解决方式来解决冲突。从效率上看，同List一样最好在 实例化对象时，即 new 时尽量确定大致数量会更加高效，另外用数值方式做Key比用类实例方式作为Key值更加高效率。从内存操作上看，大小以3->7->17->37->….的速度，每次增加2倍多的顺序进行，删除时，并不缩减内存。如果想在多线程中，共享 Dictionary 则需要进行我们自己进行lock操作。

浮点数的精度问题

  1. float基本都够用，其实double也同样有精度问题，无论怎么样都是无法避免精度导致的在逻辑中的不一致的问题。
  2. 浮点数的精度问题可不只是小数点的精度问题，随着数值越来越大，即使是整数也开始会有相同的问题，因为浮点数本身是一个 1.M * (2 ^ e) 公式形式得到的数字，当数字放大时，M的尾数的存储位数没有变化，能表达的位数有限，自然越来越难以准确表达，特别是数字的末尾部分越来越难以准确表达。
  3. 我们可以改用int或long型来替代浮点数。
  4. 用定点数保持一致性并缩小精度问题
  5. 最耗的办法，用字符串替代浮点数。
  6. 最差的办法，提高期望值。如果 1.55f / 2f 有可能等于 0.7749999 而无法达到 0.775 的目标值时，我们不妨在计算前多加个0.01，使得 1.56f / 2f，这样就大概率保证超出 0.775 的结果目标了。
  7. 如果正常浮点数的精度不能给我们安全感，那么我们就自己给自己安全感。提高自己的数值一点点，从而降低门槛跨过去的门槛，差不多的就差一点点的都当做是跨过门槛的。于是就有了 (X + 1) / Y 或者 (X + 0.001) * Y 的写法来度过’精度危机’。

委托、事件、装箱、拆箱

  1. 委托(delegate)与事件(Event)的实质在C#中万物皆是类，大部分时间里都没有指针的身影，最多也只是引用，因为指针被封装在内部函数当中。不过回调函数却依然存在，于是C#多了一个委托(delegate)的概念，所有函数指针都以委托的方式来完成的。委托可以被视为一个更高级的函数指针，它不仅仅能把地址指向另一个函数，而且还能传递参数、获得返回值等多个信息。系统还为委托对象自动生成了同步、异步的调用方式，开发人员使用 BeginInvoke、EndInvoke 方法就可以避开 Thread类 从而直接使用多线程调用。

  2. 首先不要错误的认为委托是一个语言的基本类型，我们在创建委托delegate时其实就是创建了一个delegate类实例，这个delegate委托类继承了System.MulticastDelegate类，类实例里有，BeginInvoke、EndInvoke、Invoke三个函数，分别表示，异步开始调用，结束异步调用，以及直接调用。

  3. Delegate委托类还重写了 +=，-= 这两个操作符，其实就是对应 MulticastDelegate 的 Combine 和 Remove 方法，当对函数操作 += 和 -= 时，相当于把函数地址推入了链表尾部，或者移出了链表。

  4. event 很简单，它在委托delegate上，又做了一次封装，这次封装的意义是，限制用户直接操作delegate委托实例中变量的权限。

  5. 封装后，用户不再能够直接用赋值(即使用 = 等号操作符)操作来改变委托变量了，只能通过注册或者注销委托的方法来增减委托函数的数量。也就是说被 event 声明的委托不再提供 ‘=’ 的操作符，但仍然有 ‘+=’ 和 ‘-=’ 的操作符可供操作。

    为什么要限制呢？因为在平时的编程中，由于项目太过庞大，经手的人员数量太多，导致我们常常无法得知其他人在编写的代码是什么有什么意图，这样公开的delegate委托会直接暴露在外，随时会被‘=’赋值而清空了前面累积起来的委托链表，委托的操作权限范围太大导致问题会比较严重。申明 event 后，编译器内部重新封装了委托，让暴露在外面的委托不再担心随时被清空和重置的危险。因为经过 event 封装后不再提供赋值操作来清空前面的累加，只能一个个注册或者一个个注销委托(或者说函数地址)，这样就保证了谁注册就必须谁负责销毁的目的，更好的维护了delegate的秩序。

装箱和拆箱

  1. 把值类型实例转换为引用类型实例，就是装箱。相反，把引用类型实例转换为值类型实例，就是拆箱。

  2. 值类型的变量会直接存储数据，如byte，short，int，long，float，double，decimal，char，bool 和 struct 统称为值类型，而引用类型的变量持有的是数据的引用，其真实数据存储在数据堆中，如所有的class实例的变量，string 和 class统称为引用类型。当声明一个类时，只在堆栈(堆或栈)中分配一小片内存用于容纳一个地址，而此时并没有为其分配堆上的内存空间，因此它是空的为null，直到使用 new 创建一个类的实例时，分配了一个堆上的空间，并把堆上空间的地址保存给这个引用变量，这时这个引用变量才有真正指向内存空间。

    值类型有，所有整数，浮点数，bool，以及 Struct 申明的结构，这里要注意 Struct 部分，它是经常我们犯错误的地方，常常很多人会把它当作类来使用是很错误的行为。因为它是值类型，在复制操作时是通过直接拷贝数据完成操作的，所以常常会有a、b同是结构的实例，a赋值给了b，当 b 更改了数据后发现 a 的数据却没有同步的疑问出现，事实上根本就是两个数据空间，当 a 赋值给 b 时其实并不是引用拷贝，而是整个数据空间拷贝，相当于有了a、b为两个不同西瓜，只是长得差不多而已。

    引用类型包括，类，接口，委托(委托也是类)，数组以及内置的object与string。前面说了delegate也是类，类都是引用类型，虽然有点问题也不妨碍它是一个比较好记的口号。虽然 int 等值类型也都是类，只不过它们是特殊的类，是值类型的类，因为在C#里万物皆是类。

  3. 为何需要装箱。值类型是在声明时就初始化了，因为它一旦声明就有了自己的空间因此它不可能为null，也不能为null。 而引用类型在分配内存后，它其实只是一个空壳子，可以认为是指针，初始化后不指向任何空间，因此默认为null。

  4. 栈是本着先进后出的数据结构(LIFO)原则的存储机制，它是一段连续的内存，所以对栈数据的定位比较快速, 而堆则是随机分配的空间, 处理的数据比较多, 无论如何, 至少要两次定位。堆内存的创建和删除节点的时间复杂度是O(logn)。栈创建和删除的时间复杂度则是O(1)，栈速度更快。那么既然栈速度这么快，全部用栈不就好了。这又涉及到生命周期问题，由于栈中的生命周期是必须确定的，销毁时必须按次序销毁，从最后分配的块部分开始销毁，创建后什么时候销毁必须是一个定量，所以在分配和销毁时不灵活，基本都用于函数调用和递归调用中，这些生命周期比较确定的地方。相反堆内存可以存放生命周期不确定的内存块，满足当需要删除时再删除的需求，所以堆内存相对于全局类型的内存块更适合，分配和销毁更灵活。

  5. 很多人把值类型与引用类型归类为栈和堆内存分配的区别是错误的，栈内存主要为确定性生命周期的内存服务，堆内存则更多的是无序的随时可以释放的内存。因此值类型可以在堆内也可以在栈内，引用类型的指针部分也一样可以在栈和堆内，区别在于引用类型指向的内存块都在堆内，一般这些内存块都在委托堆内，这样便于内存回收和控制，我们平时说的GC就会做些回收和整理的事。也有非委托堆内存不归委托堆管理的部分，是需要自行管理的，比如C++写了个接口生成一个内存块，将指针返回给了C#程序，这个非委托堆内存需要我们自行管理，C#也可以自己生成非委托堆内存块。

  6. 装箱： 根据相应的值类型在堆中分配一个值类型内存块，再将数据拷贝给它。按三步进行。

    第一步：在堆内存中新分配一个内存块(大小为值类型实例大小加上一个方法表指针和一个SyncBlockIndex)。

    第二步：将值类型的实例字段拷贝到新分配的内存块中。

    第三步：返回内存堆中新分配对象的地址。这个地址就是一个指向对象的引用了。

  7. 拆箱则更为简单点，先检查对象实例，确保它是给定值类型的一个装箱值，再将该值从实例复制到值类型变量的内存块中。

  8. 装箱、拆箱对执行效率有哪些影响，如何优化。

    • Struct 通过重载函数来避免拆箱、装箱。比如常用的ToString()，GetType()方法，如果 Struct 没有写重载ToString()和GetType()的方法，就会在 Struct 实例调用它们时先装箱再调用，导致内存块重新分配性能损耗，所以对于那些需要调用的引用方法，必须重载。
    • 通过泛型来避免拆箱、装箱。不要忘了 Struct 也是可以继承的，在不同的、相似的、父子关系的 Struct 之间可以用泛型来传递参数，这样就不用装箱后再传递了。比如B,C继承A，就可以有这个泛型方法 void Test(T t) where T:A，以避免使用object引用类型形式传递参数。
    • 通过继承统一的接口提前拆箱、装箱，避免多次重复拆箱、装箱。很多时候拆装箱不可避免，那么我们就让多种 Struct 继承某个统一的接口，不同的 Struct 就可以有相同的接口。把 Struct 传递到其他方法里去时就相当于提前进行了装箱操作，在方法中得到的是引用类型的值，并且有它需要的接口，避免了在方法中重复多次的拆装箱操作。比如 Struct A 和 Struct B 都继承接口 I，我们调用的方法是 void Test(I i)。当调用Test方法时传进去的 Struct A 或 Struct B 的实例都相当于提前做了装箱操作，Test里拿到的参数后就不用再担心内部再次装箱拆箱问题了。

  9. struct 值类型数据结构如果没有理解它的原理用起来可能会引起很多麻烦，切记盲目认为使用结构体会让性能提升，在没有完全彻底理解之前就冒然大量使用可能会对你的程序性能带来重创。

排序算法

  1. 快速排序算法

    • 快速排序，是种最坏情况为O(n^2)的排序算法，虽然这个最坏情况比较差但快速排序通常是用于排序的最佳的实用选择，这是因为它的平均性能比较好，其排序期望运行时间为 O(nlogn) 且 O(nlogn)记号中隐含的常数因子很小，另外还不消耗额外的内存空间，在嵌入式虚存环境中也能很好工作，因此广受人们欢迎是最常用最好用用的最多的排序算法。

    • 快速排序算法的排序步骤很简单：

      1. 从序列中选一个元素作为基准元素

      2. 把所有比基准元素小的元素移到基准元素的左边，把基准元素大的移到右边。

      3. 对分开来的二个一大一小的区块进行递归再筛选，对两个区块同样进行1、2的两个步骤处理。

    • 简单来说就是选取一个区域里的数字，把这个区域按这个数字分成两半，一半小一半大，然后继续对这两半做同样的操作，直到所有筛选都完成就完成了排序。

    • 排序算法最差的情况是，每次都选到一个最小的或最大的数字，这样每次筛选大小时都要充分移动，这种概率比较低。快速排序是最常用的排序方法，所以我们要着重优化此算法，对大量使用的算法和程序我们需要格外的重视。

    • 优化：

      1. 随机选择中轴数
      2. 三数取中
      3. 小区间使用插入排序
      4. 缩小分割范围，与中轴数相同的合并在一起

  2. 快速排序是最常用也是使用范围最广的排序算法，堆排序也是相对比较常用的，特别是堆排序的优先级队列

    • 堆排序本身结构是由完全二叉树这样的结构支撑的，普通的堆排序比快速排序更低效一点，但堆排序中的最大最小堆的优先级队列异常用有，即只关注最大或最小值，在不断增加和删除根节点元素的情况下获取最大或最小值。优先级队列在排序完成后，数据堆就成了一个头顶着一个最大值或最小值的数据结构，这种数据结构更有利于获取根节点的最大最小值节点，在后面程序逻辑中当需要插入新元素、修改旧元素、以及推出最大最小值时效率比较高。优先级队列在实时获取最大最小值时高效的特点，导致它在寻路系统的A星算法中特别有用，因此最大最小堆排序常常用于A星算法。
    • 最大最小堆的优先级队列的操作分为，插入元素，返回最大或最小值，返回并删除最大最小值，查找并修改某个元素，其中关键的算法在于插入新元素和删除最大最小元素。其基本思想是利用完全二叉树的特性将新元素放入二叉树的叶子节点上，然后比较它与父节点的大小，如果它比父节点大(最小堆的情况)则结束，否则就与父节点交换一下，继续比较直到没有父节点或者父节点比它小。删除根节点则反过来，把叶子节点放入根节点，然后找到这个新根节点的实际位置，即比较它与两个子节点大小，如果比它们小(最小堆的情况)则结束，否则取最小值(最小堆的情况)替换节点位置，然后再继续向下比较和替换，直到停止或者替换到叶子节点时再没有子节点可比较就算完成操作。

  3. 其他排序算法简要概括

    • 桶排序，把所有的元素按一定大小范围分成N个组，对每个组进行快速排序，最终得到有序的数组，并且得到N个桶的记录，虽然第一次排序的速度不怎么样，但这N个桶的信息记录下来后对于后面的程序逻辑有非常大的帮助。比如我们需要进行模糊排序或模糊搜索，这种桶信息就会有很大帮助。
    • 基数排序，是针对元素的特性来实时的‘分配式排序’，利用数字的特性按个位数，十位数，百位数的性质放入0-9的桶中不用排序，几次合并后就有了序数组，利用元素特性排序的速度比任何其他排序方式都要快速。这种算法思路教会我们在运用算法时，可以从元素的特性着手，找到它的特点就有可能找到更合适更快的算法。

搜索算法

  1. 搜索算法

    • 广度优先搜索和深度优先搜索是最常见的搜索算法，如果不进行些枝剪的话效率是比较差的，直接使用不加修饰的广度和深度算法，会消耗比较多的CPU以至于整体效率比较差。
    • 搜索算法的目的就是找东西，找出各种类型的东西，动态规划，图论，也能帮助我们很好的找到东西。好的搜索算法，大部分需要有数据结构的支撑，在数据结构里记录了信息的特征，前人的搜索的记录，和当前的内容环境，用于枝剪和优化。

  2. 二分查找算法

    • 二分查找算法是搜索中用的最多的，也是最简单易用的，效率也比较好的搜索算法。不过它有个前提条件，即查找所用的数组必须是有序的数组。也就是说，在使用二分算法查找前，必须对数组进行排序。而且在每次更改，插入，删除后都要进行排序以保证数组的有序状态。
    • 二分查找算法的步骤是：
      1. 将数组分为三块，分别是前半部分区域，中间位元素，后半部分区域。
      2. 将要查找的值和数组的中间位进行比较，若小于中间位则在前半部分查找，若大于中间位则在后半部分查找，如果等于中值时直接返回。
      3. 继续在选择的查找范围中查找，跳入1步骤，依次进行递归过程，将当前选择的范围继续拆分成前半部分，后半部分，和中间位三部分，直到范围缩小到最小，如果还是没有找到匹配的元素，就说明元素并不在数组里面。
    • 二分查找的平均时间复杂度为O(logN)，是一个效率比较好的查找算法，这也是它常被使用到的原因，不过前提是数组是有序的，可能这对于一些情况下的搜索问题的门槛会比较高，它们可能需要不停得插入或删除元素，这种情况下可以使用二分先查找到插入的位置，再做插入操作，但是插入的操作本身就是O(N)的平均时间复杂度，导致查找无论多快都还是抵不过插入带来的消耗，删除也是同样的道理，数组的拷贝操作已经成了算法中的瓶颈。我们来看看其他搜索算法是怎么做的。

  3. 二叉树、二叉查找树、平衡二叉树、红黑树、B树

    • 二叉树及其衍生的所有算法都是以父节点有且只有至多两个子节点为规则。二叉查找树就是在二叉树之上建立的查找树，主要目标是快速查找，它在构造时的特点为，左边的子节点一定比父节点小，右边的子节点一定比父节点大。算法的方式与二分查找算法有点类似，不一样在于二分查找树构建出来的树形结构，由于原始数据的排列不同有可能导致深度很大的二叉树犹如直线连接的节点，因此它也被称为是个不稳定的查找方式，搜索的速度由原始数据的排列方式决定，排列的顺序不好则速度就不佳，因此二叉树的稳定性并不高。
    • 平衡二叉树很好的解决了查找二叉树的二叉树不平衡问题，它的规则是父节点的左右两棵树的深度差的绝对值不能超过1，所有节点都遵循这个规则包括节点下的左右两棵子树叶同样遵循这个规则。二叉树的深度问题解决了，在查找时的效率就更加稳定，如果能一直保持O(logN)的时间复杂度那将是很好的算法效率。
    • 红黑树就是实现平衡二叉树的算法，都是在插入和删除节点操作时通过特定的操作保持二叉查找树的平衡，从而使二叉查找时获得较高的查找效率。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的，它能够在O(logN)时间复杂度内做查找，插入和删除操作，这里的N为二叉树中元素的数目。
    • 红黑树的数据结构特点是各节点上多了一个颜色值，颜色为红色或黑色。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。具体红黑树是怎样的算法和程序步骤不在这里介绍，有很多书本和资料可供参考。
    • 红黑树虽然高效稳定，但实际项目中运用的稍微少了点，一方面它通常会封装在自定义的底层容器算法中，例如我们通常会重新封装Map、Dictionary容器，把红黑树放入容器中使得写业务逻辑的同学能够不需要关心底层的算法的情况下高效的使用容器。另一方面它的算法复杂度高，一般程序员需要费点心思去研究，因此通常也不会方在明显的位置上使用，这也是红黑树一般都会放入容器里使用的原因之一，它也更适合容器类外壳。还有一方面，查找可以用“快速排序”+“二分查找”代替，效率稍差一些但简单实用，使用优化后的快速排序效率在查找效率上会优于红黑树，如果逻辑中查找的次数远远大于插入与删除的次数，则可以考虑用“快速排序”+“二分查找”代替这种方式进行替代。
    • B树大家听的也比较多，其实它主要是为磁盘存储设备而设计的一种平衡查找树。它与红黑树主要不同在于，B树是建立在查找树之上的多叉树，它的一个节点上有多个值且父节点可以拥有2个以上的节点，同时还必须保持平衡树的层次结构，即树的深度值不得超过logN的深度(N为节点个数)。这种数据结构犹如在红黑树之上建立多叉的方式，其比较方式由单一值比较改为了多值比较。在B树结构里一个节点里的信息是个数组，它们是有序的，因此可用二分查找法查找数据，若没有找到准确值，则继续往下搜索子节点的数据。B树在游戏项目中里很少用到，不过它在文件信息存储结构上能发挥巨大作用，这也是它被开发出来的原因之一，其他包括B+和B*树都是从B树衍生而来。