什么是OrderBook

OrderBook是一个包含了所有交易者信息的订单集合，他们想买或者想卖。想买的order叫做bid，想卖的order叫做ask，这些bid和ask的order一旦满足了各自的条件，就会尽可能快的完成配对，促成一笔交易。这里有两个种类的order需要介绍一下，它们也是最为基本的交易订单。第一种是市价 market order，买和卖都是依据当前在orderbook能寻找到的最优价格执行。第二种是限价 limit order，买和卖都是按照已经确定量和价格进行。OrderBook是传统金融中一个很重要的交易方式，通过OrderBook中显示的信息，可以判断当前市场的供需关系以及价格关系，基于以上的判断可以对市场中的下一步发生的变化进行一个判断。在去中心化金融(Defi)，刚开始发展时也借鉴到了OrderBook的模式，由于传统的OrderBook由中心化机构进行给出，导致了信息中心化不透明。所以在Defi中想实现一个OrderBook完全只有买方和卖方进行参与，而机构只收取相依的手续费即可。
看起来这样的想法是一种很不错的想法，提供了一个更加公平和自由度更高的一个市场让人们去操作。但是在实际中进行时会发现问题：

• 对于OrderBook需求来说整个区块链网络中交易成交的速率和数量都无法满足，即使以太坊的速率相较于比特币网络有了很大的提高。
• 在交易中有gas的存在，如果没有一种很好的方法去定位到合适的订单的话，随着订单数量的变多，找到相应订单所需的gas会消耗很大。并且每笔交易都有一个gas上限，当gas达到相应上限的时候就会导致交易失败。

  实现OrderBook思路

  一般的思路

  抛开以太坊特殊的条件，我们在实现OrderBook的时候，采用的最常用的方法就是蛮力法。思路：

  • 创建买单和买单两个数组
  • 当有买单创建的时候，对买单数组进行遍历，找到对应价格对应数量的订单，完成一笔交易。如果没找到，将买单加入买单数组。同理创建卖单时也进行相应的操作。

这个方法能确保找到所需要的的交易，但是整个过程的时间复杂度为O(n),然后可以进行并发和互斥锁结合，可以在短时间内处理大量的买单和买单满足需求。但是随着订单量的增多，所需要的时间也会增多，这在链上和链下的环境中都是不能接受的。
但是，如果不采用蛮力法的话，将买单和卖单分别用排序二叉树的方式进行数据保存，那样的话时间复杂度就会变为O(logn)，这样可以优化查找，只是在插入是有点麻烦。

换种思路

在智能合约中我们要尽量避免时使用循环的方式，这是很费gas的。而为了确保能够得到想要的价格。我们可以这样设计：

• 创建两个买单和卖单的两个映射
  • mapping(uint => mapping(uint => address[])) Bid;
  • mapping(uint => mapping(uint => address[])) Ask;
  • 前一个uint是价格，第二个uint是数量，最后面的是卖方或买方的地址；
• 每次有买单和卖单进来的时候，在mapping中进行搜索，完成交易。搜索不到的话加入对应的mapping中即可。

看上去这样的两个映射可以解决买卖双方的订单的查找的时间复杂度问题（将时间复杂度降为O(1)）。但是这样却忽略了一个问题，这样做我们无法看到整个市场的变化和趋势。我们这样设计代码的话只是实现了OrderBook的一部分功能。如果想要实现OrderBook，还有很多要进行修改的地方。

第三种思路

在链上尽量不要使用大循环，但是我们可以将大循环变为小的循环，这样来说是可以的。同时我们也要反映整个OrderBook的变化，我们就可以设计一个压缩前缀树：

• 树中的每个节点为数字0~9，这样从头结点到叶子节点前的节点就可以连成一串数字，这个数字表示金额，每个叶子节点储存的是订单数组，每个订单保存了在此金额下的数量和地址。
• 同样树也要分两颗树，买家树和卖家树。
• 每次有新金额出现时，要对树进行修改，对树进行扩展，保证从头到尾连成的数字为金额。
• 同时当金额对应的叶子节点中数组长度为0时，要对树进行删除，这样做的目的是保证在对树遍历时减少时间消耗。
• 在新买单创建时，先在卖家树中找到对应金额的数组，在对数组进行遍历找到对应金额(此时就将大循环优化为一个小循环)，找到对应订单后就成交交易。没找到的话就将其加入买家树。(同理，卖单也是这样处理)

这样的话就可以兼顾市场变化和挂单的需求。

问题

以上的思路都可以实现OrderBook，但是还有许多问题需要进行考虑：

• 如果对应的数量找不到，但是存在两个或两个以上的订单之和满足要求的时候，要怎么进行处理？在时间复杂度较小的前提下如何完成这个拆分寻找的过程？
• 整个树的结构要如何设计？才能使得在增删改查较为方便？

结尾

虽然现在主流的DEX没有使用OrderBook，而是使用LP这样的方式，但是LP也会存在着很多的问题需要解决。正是因为OrderBook的一些功能无法满足Defi的需求，所以才会有LP的出现。技术的适用性是需要结合需求的。或许在以后可能会产生适应区块链的OrderBook。