一、需要存储行情的tick数据，查找起来比较快的数据结构

1、哈希表

哈希表是一种基于哈希函数实现的数据结构，使用哈希函数可以将数据映射到一个固定长度的数组中，从而实现常数时间内的查找、插入和删除操作。在存储行情tick数据时，可以将每个tick的时间戳作为键，将其余信息作为值进行存储。这样可以在需要查找某个时间点的tick数据时，通过时间戳快速定位到对应的tick数据。

哈希表的特点：

访问速度很快：由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。需要额外的空间：首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。无序：散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。可能会产生碰撞：没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。

2、平衡树

平衡树包括红黑树、AVL树等，它们可以帮助我们保持数据的有序性。在存储tick数据时，可以按照时间戳为键进行排序，在需要查找某个时间段内的tick数据时，可以利用平衡树的查找时间为对数级别的特点，快速定位到对应的tick数据。

平衡二叉树的特点：

非叶子节点非常多拥有两个子节点；非叶子节值大于左边子节点、小于右边子节点；树的左右两边的层级数相差不会大于1；没有值相等重复的节点。

二、tick数据简介

Tick Data本身并不神秘，就是交易所把每只股票（亦或是futures options）的active order book（你的委托还存在在交易所里面，但并且没有成交）里面的买、卖的单的情况发给你。Tick 一般是指 Best Bid/Offer 的变化，就是 Order Book 上优异的买单和卖单发生的变化。Tick 2 和 Tick 1 的不同就在于 Best Offer 的 size 变了（少了 25），所以产生了这一个 tick。当然这个不等于说 Tick 1 和 Tick 2 之间没有别的 Order Book 的变化，它可以在除了 Best Bid/Offer 之外的地方变化，只不过这些事情在 Tick Data 上被滤掉了而已。

这种所谓的 Tick Data 其实就是一种对 Order Book Events 的 Down Sample 而已，它的前提假设是 Best Bid/Offer 是最重要的信息，以丢弃其它相对不如这个重要的信息为代价，缩减数据规模，让数据处理变的更容易。而实际上，真正的 Limit Order Book Market 里，交易所发的原始数据是所有对 Order Book 的增、删、改＋成交这四样，特别是改单一般都是占整体数据流的大部分。只不过要处理这种级别的数据，需要使用数据结构的操作，维护重建 Order Book。

优异质的tick包含两部分，一是orderbook每一笔订单的挂单、撤单；二是逐笔成交。一般交易所提供的深度都是快照，但也提供了每笔挂单数据，可以本地维护订单重建全深度。期货那种1s两次，也不提供逐笔成交的tick只是一个半残数据。下面提供一个简单的Bitmex深度更新推送重建orderbook的部分代码：

if event == 'orderBookL2':    data = msg['data']    symbol = data[0]['symbol'].lower()    if msg['action'] == 'partial':        _cache[symbol+'asks'] = {}        _cache[symbol+'bids'] = {}    for ele in data:        if symbol == 'xbtusd':            price = (1e8*88-int(ele['id']))*0.01        else:            price = (297*1e8-int(ele['id']))/20        if ele['side'] == 'Buy':            if msg['action'] == 'delete':                del _cache[symbol+'bids'][price]            else:                _cache[symbol+'bids'][price] = float(ele['size'])        else:            if msg['action'] == 'delete':                del _cache[symbol+'asks'][price]            else:                _cache[symbol+'asks'][price] = float(ele['size'])    a = sorted([[k,v] for k,v in _cache[symbol+'asks'].items()])[:50]    b = sorted([[k,v] for k,v in _cache[symbol+'bids'].items()], reverse=True)[:50]

三、数据结构简介

数据结构是一种计算机科学技术领域广泛使用的专业术语，在很多书籍以及博客中，对数据结构的解释为数据在计算机的存储方式，很容易让人误以为数据结构只是一种数据的物理存储方式，其实不然，数据结构可以理解为：数据 + 结构。数据是描述客观事物的符号，为程序操控，存储在计算机上，结构包括数据的逻辑结构和存储结构。

根据数据元素间关系的不同特性，通常有下列四类基本的结构：

集合结构：该结构的数据元素间的关系是“属于同一个集合”。线性结构：该结构的数据元素之间存在着一对一的关系。树型结构：该结构的数据元素之间存在着一对多的关系。图形结构：该结构的数据元素之间存在着多对多的关系，也称网状结构。 从上面所介绍的数据结构的概念中可以知道，一个数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。

常见的数据结构：

栈（Stack）：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。队列（Queue）：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。数组（Array）：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。链表（Linked List）：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。树（Tree）：树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。堆（Heap）：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。散列表（Hash table）：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

延伸阅读1：数据结构的常用运算

检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。插入：往数据结构中增加新的节点。删除：把指定的结点从数据结构中去掉。更新：改变指定节点的一个或多个字段的值。排序：把节点按某种指定的顺序重新排列。例如递增或递减。