应用于键树的编码方法、应用于键树的解码方法与电子装置

技术领域

本发明关于数据管理，尤指一种应用于键树的编码方法、应用于键树的解码方法与相关的电子装置。

背景技术

随着因特网上数据量的快速成长，使用键值(key-value)的组合来对大量数据进行组织与管理已越来越普遍，因此，如何有效存储键值并通过输入键来快速获取相对应的值便成为一项重要课题。一般而言，多个键可根据左“0”右“1”的典型二元树(binary tree)架构而构成键树(key Trie)的树状结构，当接收到输入键时，可基于键树的树状结构来找出对应此输入键的叶节点，并根据此叶节点来获取出相对应的值，然而，当构成键树的多个键的长度很长时，若基于键树来直接进行搜寻，便需要很大的内存容量来完整存储键树的数据，且需要进行大量对比运算才能找出此输入键于此键树中的相对应叶节点。

发明内容

因此，本发明的目的之一在于提出一种应用于键树的编码方法、应用于键树的解码方法与相关的电子装置。

在本发明的一个实施例中，公开一种应用于一键树的编码方法。该编码方法包含有：针对该键树中部分的非叶节点进行编码，以产生多笔元数据；以及将该键树的一编码结果写入一存储装置，其中该编码结果包含该部分的非叶节点所分别对应的该多笔元数据。

在本发明的另一个实施例中，公开一种应用于一键树的解码方法。该解码方法包含：自一存储装置读取该键树的一编码结果所包含的多笔元数据中的一笔元数据，其中该笔元数据包含一相对应非叶节点于该键树中的一深度值；根据一输入键中对应该深度值的一位的位值，来选择性地更新一键索引值；以及根据该位所指示的该相对应非叶节点的一单侧子树的叶节点总数，来判断该键索引值的解码操作是否结束。

在本发明的另一个实施例中，公开一种电子装置。该电子装置包含一存储装置以及一处理电路。该处理电路用以针对一键树中部分的非叶节点进行编码，以产生多笔元数据；以及将该键树的一编码结果写入一存储装置，其中该编码结果包含该部分的非叶节点所分别对应的该多笔元数据。

在本发明的另一个实施例中，公开一种电子装置。该电子装置包含一存储装置以及一处理电路。该处理电路用以自该存储装置读取一键树的一编码结果所包含的多笔元数据中的一笔元数据，其中该笔元数据包含一相对应非叶节点于该键树中的一深度值；根据一输入键中对应该深度值的一位的位值，来选择性地更新一键索引值；以及根据该位所指示的该相对应非叶节点的一单侧子树的叶节点总数，来判断该键索引值的解码操作是否结束。

关于编码操作，假设键群组所包含的多个键的个数为N以及键的最大长度为M个位，由于键树中每个分支度为2的非叶节点会编码为一笔元数据(D,NL)，其中深度值D需要log

附图说明

图1为根据本发明一实施例的电子装置的示意图。

图2为属于同一键群组的多个键的列表。

图3为多个键所对应的键树的示意图。

图4为根据本发明一实施例的应用于键树的编码方法的流程图。

图5为图3所示的键树经由图4所示的编码流程进行处理的操作示意图。

图6为图3所示的键树经由图4所示的编码流程进行处理所产生的编码结果的示意图。

图7为根据本发明一实施例的应用于键树的解码方法的流程图。

图8为键树的编码结果经由图7所示的解码流程进行处理来产生输入键的键索引值的示意图。

具体实施方式

图1为根据本发明一实施例的电子装置的示意图。如图1所示，电子装置100包含(但不局限于)处理电路102以及存储装置104，例如处理电路102可以是一般用途处理器(general purpose processor)、现场可程序化逻辑门阵列(field programmable logicgate,FPGA)或是任何具备运算能力的电路，而存储装置104则可以是晶载内存(on-chipmemory)、芯片外内存(off-chipmemory)或是任何具备数据暂存能力的存储组件。本实施例中，电子装置100可通过加载并执行程序代码来实现本发明应用于键树的编码方法与解码方法，此外，电子装置100可应用于管理分布式存储系统的键值数据库(key-valuestore)中多个键所对应的键树，举例来说，分布式存储系统可以是对象存储(object storage)系统，以及键值数据库的键可经由排序而划分为多个键群组(key group)，而每个键群组可包含多个键(亦即键值数据库中一部分的键)并据此建构出一个键树，而本发明的编码方法与解码方法可应用于每个键群组所对应的键树。

假设键群组所包含的多个键的个数为N，则键树便会具有N个叶节点。另外，假设键的最大长度为M个位，则键树的深度便会是M，当电子装置100所要管理的键是来自分布式存储系统(例如对象存储系统)，由于很多对象需要被识别，因此，键的长度有可能达到256个字节或甚至更长。为了便于说明本发明编码方法与解码方法的技术内容，以下实施例便假设所要处理的键群组包含9个键KA,KB,KC,KD,KE,KF,KG,KH,KI(N＝9)，以及键的最大长度为10个位(M＝10)。图2为属于同一键群组的9个键KA～KI的列表，而图3则是9个键KA～KI所对应的键树300的示意图，其中叶节点L0～L8分别对应键KA～KI，另外，于本实施例中，由左至右，键KA～KI的键索引值(key index)分别设定为0～8。

为了能快速地从键树的这些键中快速地搜寻出所要的键，本发明编码方法会对键树进行编码处理并产生元数据(meta data)来作为键树的编码结果，其中元数据包含跟这些键有关的索引信息。相较于针对键树300中全部的非叶节点(non-leaf node)均进行编码，本发明编码方法可以针对键树300中部分的非叶节点(例如分支度大于1的节点)进行编码，如此一来，当键树300中部分的非叶节点需进行编码以及部分的非叶节点不需进行编码时，由于实际进行编码处理的非叶节点个数小于所有非叶节点的总数，故可提高编码效率并减少编码结果所需占用的存储空间。如图3，键树300是根据左“0”右“1”的典型二元树架构而构成的树状结构，而根据二元树本身的特性，假设叶节点的个数为n0以及分支度(degree)为2的节点的个数为n2，则n0＝n2+1，此外，仅有分支度为2的节点会跟键的偏移有关，根据这些观察到的特性，于本发明的一个实施例中，编码方法便可以针对键树300中部分的非叶节点(例如分支度为2的节点)进行编码以产生多笔元数据，以及将键树300的编码结果MD写入存储装置104，其中编码结果MD包含部分的非叶节点(例如分支度为2的节点)所分别对应的多笔元数据。

图4为根据本发明一实施例的应用于键树的编码方法的流程图。请注意，假若可以得到相同结果，则步骤不一定要完全遵照图4所示的顺序来依序执行。编码方法由处理电路102所执行，例如处理电路102可加载并执行程序代码来产生键树的编码结果MD。编码方法会从深度为0的根节点(root node)开始，基于深度优先遍历(depth first traversal)的次序来依序判断键树中每个非叶节点是否需要进行编码。当判断目前的非叶节点需要编码时，记录一笔元数据来作为此非叶节点的编码输出，并根据深度优先遍历的次序来继续下个非叶节点的处理。当判断目前的非叶节点不需要编码时，无需记录此非叶节点的元数据，并同样根据深度优先遍历的次序来继续下个非叶节点的处理。编码方法会持续检查键树中的非叶节点，直到键树中所有分支度为2的非叶节点均完成编码为止。进一步的操作说明如下。

于步骤402，编码方法先处理根节点，其深度为0，因此，目前待处理的非叶节点的深度值D设定为0(亦即D＝0)，以及目前待处理的非叶节点所关联的叶节点总数LC设定为N(亦即LC＝N)，以图3所示的键树300为例，根节点所关联的叶节点总数即为键树300所包含的所有键KA～KI的个数，因此N＝9。

于步骤404，编码方法会计算位于深度值D的目前待处理的非叶节点的左子树叶节点总数(left sub-Trie leaf count)NL以及右子树叶节点总数(rightsub-Trie leafcount)RL，请注意，步骤402所设定的叶节点总数LC会等于步骤404所得到的左子树叶节点总数NL与右子树叶节点总数RL的总和，亦即LC＝NL+RL。

于步骤406，编码方法会检查左子树叶节点总数NL是否大于0以及右子树叶节点总数RL是否大于0。若左子树叶节点总数NL与右子树叶节点总数RL两者均大于0，则表示位于深度值D的目前待处理的非叶节点为分支度为2的非叶节点，因此编码方法会执行步骤408。若左子树叶节点总数NL与右子树叶节点总数RL中仅有一个数值大于0，则表示位于深度值D的目前待处理的非叶节点为分支度为1的非叶节点，因此编码方法会执行步骤410。

于步骤408，由于位于深度值D的目前待处理的非叶节点是判断为分支度为2的非叶节点，因此会针对此非叶节点进行编码来记录相对应的一笔元数据。元数据会包含此非叶节点于键树中的深度值以及此非叶节点的一单侧子树的叶节点总数，于本实施例中，元数据记录深度值D以及左子树叶节点总数NL，亦即(D,NL)。另外，针对此非叶节点的左子树的后续处理，编码方法会将深度值D加1来更新深度值D(亦即D＝D+1)，以及叶节点总数LC会更新为左子树叶节点总数NL(亦即LC＝NL)；针对此非叶节点的右子树的后续处理，编码方法会将深度值D加1来更新深度值D(亦即D＝D+1)，以及叶节点总数LC会更新为右子树叶节点总数RL(亦即LC＝LC-NL＝RL)。后续会根据相同的编码操作来递归(recursive)处理此非叶节点的左子树中的非叶节点，然而，当此非叶节点的左子树所具有的叶节点总数LC没有大于1，这代表较大深度没有任何需要编码的分支度为2的非叶节点，故编码方法此时会结束此左子树的后续编码处理；同样地，会根据相同的编码操作来递归处理此非叶节点的右子树的非叶节点，然而，当此非叶节点的右子树所具有的叶节点总数LC没有大于1，这代表较大深度没有任何需要编码的分支度为2的非叶节点，故编码方法此时会结束此右子树的后续编码处理。

于步骤410，由于位于深度值D的目前待处理的非叶节点是判断为分支度为1的非叶节点，因此不会针对此非叶节点进行编码来记录相对应的元数据。编码方法会判断左子树叶节点总数NL与右子树叶节点总数RL中是那一个数值大于0，并判断此数值是否大于1。若左子树叶节点总数NL大于1，则表示此非叶节点的左子树于较大深度仍存在需要编码的分支度为2的非叶节点，故编码方法会执行步骤412，将深度值D加1来更新深度值D(亦即D＝D+1)，以及叶节点总数LC会更新为左子树叶节点总数NL(亦即LC＝NL)，后续会根据相同的编码操作来递归处理左子树中的非叶节点。若右子树叶节点总数RL大于1，则表示此非叶节点的右子树于较大深度仍存在需要编码的分支度为2的非叶节点，故编码方法会执行步骤414，将深度值D加1来更新深度值D(亦即D＝D+1)，以及叶节点总数LC会更新为右子树叶节点总数RL(亦即LC＝LC-NL＝RL)，后续会根据相同的编码操作来递归处理右子树中的非叶节点。若左子树叶节点总数NL不大于1，则表示此非叶节点的左子树于较大深度并不会存在任何需要编码的分支度为2的非叶节点，故可跳过此非叶节点的左子树的编码处理；同理，若右子树叶节点总数RL不大于1，则表示此非叶节点的右子树于较大深度并不会存在任何需要编码的分支度为2的非叶节点，故可跳过此非叶节点的右子树的编码处理。

通过图4所示的编码流程，可以找出每个分支度为2的非叶节点并进行编码来产生相对应的一笔元数据以作为编码输出，请一并参阅图5与图6，图5为图3所示的键树300经由图4所示的编码流程进行处理的操作示意图，而图6为图3所示的键树300经由图4所示的编码流程进行处理所产生的编码结果MD的示意图。一开始，编码流程从根节点N0开始处理，步骤402将深度值D设定为根节点N0的深度(D＝0)以及将叶节点总数LC设定为键树300中所有键KA～KI的个数(LC＝9)，接着，步骤404得到根节点N0的左子树叶节点总数NL为6(NL＝6)与右子树叶节点总数RL为3(RL＝3)，因此，步骤406判断左子树叶节点总数NL与右子树叶节点总数RL两者均大于0，故步骤408会对根节点N0(其为非叶节点)进行编码来记录一笔元数据(0,6)，亦即(D,NL)＝(0,6)。针对根节点N0的左子树的后续处理，步骤408更新深度值D为1(亦即D＝D+1＝0+1＝1)，以及设定叶节点总数LC为NL(亦即LC＝NL＝6)，由于叶节点总数LC大于1，因此，后续会对根节点N0的左子树继续编码处理。针对根节点N0的右子树的后续处理，步骤408更新深度值D为1(亦即D＝D+1＝0+1＝1)，以及设定叶节点总数LC为RL(亦即LC＝LC-NL＝RL＝3)，由于叶节点总数LC大于1，因此，后续会对根节点N0的右子树继续编码处理。

基于深度优先遍历的次序，编码方法后续会先对根节点N0的左子树进行处理，由于步骤408已针对根节点N0的左子树而将深度值D更新为1，因此，根节点N0的左子树中首先要处理的节点为N1，步骤404得到节点N1的左子树叶节点总数NL为2(NL＝2)与右子树叶节点总数RL为4(RL＝4)，因此，步骤406判断左子树叶节点总数NL与右子树叶节点总数RL两者均大于0，故步骤408会对节点N1(其为非叶节点)进行编码来记录一笔元数据(1,2)，亦即(D,NL)＝(1,2)。针对节点N1的左子树的后续处理，步骤408更新深度值D为2(亦即D＝D+1＝1+1＝2)，以及设定叶节点总数LC为NL(亦即LC＝NL＝2)，由于叶节点总数LC大于1，因此，后续会对根节点N1的左子树继续编码处理。针对节点N1的右子树的后续处理，步骤408更新深度值D为2(亦即D＝D+1＝1+1＝2)，以及设定叶节点总数LC为RL(亦即LC＝LC-NL＝RL＝4)，由于叶节点总数LC大于1，因此，后续会对根节点N1的右子树继续编码处理。

基于深度优先遍历的次序，编码方法后续会先对节点N1的左子树进行处理，由于步骤408已针对节点N1的左子树而将深度值D更新为2，因此，节点N1的左子树中首先要处理的节点为N2，步骤404得到节点N2的左子树叶节点总数NL为2(NL＝2)与右子树叶节点总数RL为0(RL＝0)，因此，步骤406判断左子树叶节点总数NL与右子树叶节点总数RL中仅有左子树叶节点总数NL大于0，故步骤410判断后续流程要处理节点N2的左子树而无需处理节点N2的右子树，故针对节点N2的左子树的后续处理，步骤412更新深度值D为3(亦即D＝D+1＝2+1＝3)，以及设定叶节点总数LC为NL(亦即LC＝NL＝2)，由于叶节点总数LC大于1，因此，后续会对根节点N2的左子树继续编码处理。

基于深度优先遍历的次序，编码方法后续会对节点N2的左子树进行处理，由于步骤408已针对节点N2的左子树而将深度值D更新为3，因此，节点N2的左子树中首先要处理的节点为N3，步骤404得到节点N3的左子树叶节点总数NL为2(NL＝2)与右子树叶节点总数RL为0(RL＝0)，因此，步骤406判断左子树叶节点总数NL与右子树叶节点总数RL中仅有左子树叶节点总数NL大于0，故步骤410判断后续流程要处理节点N3的左子树而无需处理节点N3的右子树，故针对节点N3的左子树的后续处理，步骤412更新深度值D为4(亦即D＝D+1＝3+1＝4)，以及设定叶节点总数LC为NL(亦即LC＝NL＝2)，由于叶节点总数LC大于1，因此，后续会对根节点N2的左子树继续编码处理。

同理，由于节点N4～N8均是分支度为1的节点并仅具有左子树，针对节点N4的左子树的后续处理，步骤412更新深度值D为5，以及设定叶节点总数LC为2；针对节点N5的左子树的后续处理，步骤412更新深度值D为6，以及设定叶节点总数LC为2；针对节点N6的左子树的后续处理，步骤412更新深度值D为7，以及设定叶节点总数LC为2；针对节点N7的左子树的后续处理，步骤412更新深度值D为8，以及设定叶节点总数LC为2；以及针对节点N8的左子树的后续处理，步骤412更新深度值D为9，以及设定叶节点总数LC为2。

基于深度优先遍历的次序，编码方法后续会对节点N8的左子树进行处理，由于步骤408已针对节点N8的左子树而将深度值D更新为9，因此，节点N8的左子树中首先要处理的节点为N9，步骤404得到节点N9的左子树叶节点总数NL为1(NL＝1)与右子树叶节点总数RL为1(RL＝1)，因此，步骤406判断左子树叶节点总数NL与右子树叶节点总数RL两者均大于0，故步骤408会对节点N9(其为非叶节点)进行编码来记录一笔元数据(9,1)，亦即(D,NL)＝(9,1)。针对节点N9的左子树的后续处理，步骤408更新深度值D为10(亦即D＝D+1＝9+1＝10)，以及设定叶节点总数LC为NL(亦即LC＝NL＝1)，由于叶节点总数LC没有大于1，因此后续会直接跳过节点N9的左子树的处理。针对节点N9的右子树的后续处理，步骤408更新深度值D为9(亦即D＝D+1＝9+1＝10)，以及设定叶节点总数LC为RL(亦即LC＝LC-NL＝RL＝1)，由于叶节点总数LC没有大于1，因此后续会直接跳过节点N9的右子树的处理。

基于深度优先遍历的次序，编码方法后续会依序针对节点N1的右子树进行处理、节点N10的左子树进行处理、节点N10的右子树进行处理、节点N0的右子树进行处理以及节点N13的右子树进行处理，由于熟习技艺者可基于上述说明书段落的内容而轻易得知后续的编码操作，为了简洁起见，后续编码操作的说明便于此不再赘述。

根据图4所示的流程，编码方法会基于深度优先遍历的次序而依序对分支度为2的非叶节点N0、N1、N9、N10、N11、N12、N13、N14进行编码，并分别产生相对应的元数据D0、D1、D2、D3、D4、D5、D6、D7，如图6所示，键树300的编码数据MD会包含8笔元数据D0～D7，每笔元数据记录深度值D与左子树叶节点总数NL，相较于键树300中多个键KA～KI的数据量(例如每个键的长度有可能达到256个字节或甚至更长)，编码数据MD的数据量会比较小(例如每笔元数据中的深度值D与左子树叶节点总数NL可使用较少的位数来记录)，换言之，相较于将多个键KA～KI存储于存储装置104来进行输入键的搜寻，将编码数据MD存储于存储装置104来进行输入键的搜寻仅需占用较小的存储空间，另外，如前所述，基于二元树本身的特性，假设叶节点的个数为n0以及分支度为2的节点的个数为n2，则n0＝n2+1，因此，在键树300中多个键KA～KI的个数是已知的情况下，编码数据MD所包含的多笔元数据D0～D7的个数也是已知的，因此，编码数据MD的数据量可事先得知来规划存储装置104的存储空间。

当处理电路102自分布式存储系统(例如对象存储系统)接收一输入键K_IN，可基于输入键K_IN与存储装置104中所存储的编码数据MD来进行解码操作，以得到对应于输入键K_IN的键索引值，以图3所示的键树300为例，由左至右，键KA～KI的键索引值分别为0～8，若解码操作最后得到的键索引值为K_IDX，则表示输入键K_IN可能是键KA～KI中具有此键索引值K_IDX的键。

图7为根据本发明一实施例的应用于键树的解码方法的流程图。请注意，假若可以得到相同结果，则步骤不一定要完全遵照图7所示的顺序来依序执行。解码方法由处理电路102所执行，例如处理电路102可加载并执行程序代码来得到解码结果(亦即输入键K_IN所对应的键索引值K_IDX)。解码方法会自存储装置104读取键树的编码结果MD所包含的多笔元数据中的一笔元数据，其中该笔元数据包含一相对应非叶节点于键树中的一深度值；根据输入键K_IN中对应该深度值的一位的位值，来选择性地更新一键索引值；以及根据该位所指示的该相对应非叶节点的一单侧子树的叶节点总数，来判断该键索引值的解码操作是否结束。若判断该键索引值的解码操作尚未结束，后续则会自存储装置104读取另外一笔元数据来继续解码。解码方法会不断读取编码结果MD中的元数据，直到该键索引值的解码操作结束为止。进一步的操作说明如下。

于步骤702，解码方法先针对一些参数进行初始化，将键索引值K_IDX设为初始值0(K_IDX＝0)，将目前的解码节点位置D_PTR设为初始值0(D_PTR＝0)，并将叶节点总数LC设定为初始值N(LC＝N)。以图3所示的键树300为例，根节点所关联的叶节点总数即为键树300所包含的所有键的个数，因此，叶节点总数LC的初始值N会等于9(N＝9)。另外，以图6所示的键树300的编码结果MD为例，多笔元数据D0～D7所分别对应的解码节点位置D_PTR分别为0～7，因此，解码方法会从解码节点位置D_PTR＝0的元数据D0开始进行解码。

于步骤704，解码方法会判断叶节点总数LC是否等于1。若叶节点总数LC等于1，则表示已经基于输入键K_IN而于键树中找到对应的叶节点，因此，键索引值的解码操作便可以结束。若叶节点总数LC大于1，这代表尚未基于输入键K_IN而于键树中找到对应的叶节点，因此，键索引值的解码操作还要继续执行。

于步骤706，解码方法会基于目前的解码节点位置D_PTR进行解码，以自存储装置104读取键树的编码结果MD所包含多笔元数据中的一笔元数据，如前所述，每一笔元数据会记录深度值D以及左子树叶节点总数NL。步骤706进行元数据解码所得到的深度值D会使用于步骤708，而步骤706进行元数据解码所得到的左子树叶节点总数NL则会基于步骤710的判断结果而使用于步骤712或是步骤714。

于步骤708，解码方法自输入键K_IN中读取对应深度值D的位的位值。

于步骤710，解码方法会检查输入键K_IN中对应深度值D的位的位值为1还是0。若是0，则执行步骤712。若是1，则执行步骤714。

于步骤712，解码方法会将叶节点总数LC更新为左子树叶节点总数NL(亦即LC＝NL)，另外，将目前的解码节点位置D_PTR加1(亦即D_PTR＝D_PTR+1)，此外，目前的键索引值K_IDX则保持不变。解码流程接着会回到步骤704来判断键索引值K_IDX的解码操作是否结束。

于步骤714，解码方法会将叶节点总数LC更新为右子树叶节点总数(亦即LC＝LC-NL＝RL)，另外，将目前的解码节点位置D_PTR加上左子树叶节点总数NL(亦即D_PTR＝D_PTR+NL)，此外，目前的键索引值K_IDX也会加上左子树叶节点总数NL(亦即K_IDX＝K_IDX+NL)。解码流程接着会回到步骤704来判断键索引值K_IDX的解码操作是否结束。

当步骤704判断键索引值K_IDX的解码操作已结束，则解码方法接着执行步骤716来对输入键K_IN进行验证。由于键树300中多个键KA～KI的数据量大，因此，实作上会存储于电子装置100的外部存储装置，例如传统硬盘或固态硬盘(solid-state drive)，于步骤716，解码方法会根据最终解码得到的键索引值K_IDX来取得相对应键的存储地址ADDR，并据此至外部存储装置读取记录于存储地址ADDR的相对应键，接着对比输入键K_IN与外部存储装置所获取的相对应键。若两者相符，则表示输入键K_IN的搜寻正确，因此后续便可自外部存储装置读取输入键K_IN所配对的值。若两者不符，则表示输入键K_IN并不隶属于键树300。

通过图7所示的解码流程，可以从键树300的编码数据MD所提供的索引信息来决定出输入键K_IN的键索引值K_IDX，请一并参阅图5与图8，图8为键树300的编码结果MD经由图7所示的解码流程进行处理来产生输入键K_IN的键索引值K_IDX的示意图。假设所要解码的输入键K_IN为键KF(亦即K_IN＝0101000110)，一开始时，步骤702分别将键索引值K_IDX设为0，目前的解码节点位置D_PTR设为0，并将叶节点总数LC设定为初始值9。由于叶节点总数LC此时不等于1，因此，步骤706基于目前的解码节点位置D_PTR来对元数据D0进行解码而取得深度值0(D＝0)与左子树叶节点总数6(NL＝6)。步骤708取得输入键K_IN位于深度值0的位的位值为0，因此，步骤710判断后续要执行步骤712，故步骤712会让键索引值K_IDX仍保持为0，将目前的解码节点位置D_PTR更新为1(D_PTR＝D_PTR+1)，并将叶节点总数LC更新为6(LC＝NL)。

解码流程接着回到步骤704。由于叶节点总数LC此时仍不等于1，因此，步骤706基于目前的解码节点位置D_PTR来对元数据D1进行解码而取得深度值1(D＝1)与左子树叶节点总数2(NL＝2)。步骤708取得输入键K_IN位于深度值1的位的位值为1，因此，步骤710判断后续要执行步骤714，故步骤714会让键索引值K_IDX更新为2(K_IDX＝K_IDX+2)，将目前的解码节点位置D_PTR更新为3(D_PTR＝D_PTR+2)，并将叶节点总数LC更新为4(LC＝LC-NL)。

解码流程接着回到步骤704。由于叶节点总数LC此时仍不等于1，因此，步骤706基于目前的解码节点位置D_PTR来对元数据D3进行解码而取得深度值3(D＝3)与左子树叶节点总数2(NL＝2)。步骤708取得输入键K_IN位于深度值3的位的位值为1，因此，步骤710判断后续要执行步骤714，故步骤714会让键索引值K_IDX更新为4(K_IDX＝K_IDX+2)，将目前的解码节点位置D_PTR更新为5(D_PTR＝D_PTR+2)，并将叶节点总数LC更新为2(LC＝LC-NL)。

解码流程接着回到步骤704。由于叶节点总数LC此时仍不等于1，因此，步骤706基于目前的解码节点位置D_PTR来对元数据D5进行解码而取得深度值7(D＝7)与左子树叶节点总数1(NL＝1)。步骤708取得输入键K_IN位于深度值7的位的位值为1，因此，步骤710判断后续要执行步骤714，故步骤714会让键索引值K_IDX更新为5(K_IDX＝K_IDX+1)，将目前的解码节点位置D_PTR更新为6(D_PTR＝D_PTR+1)，并将叶节点总数LC更新为1(LC＝LC-NL)。

解码流程接着回到步骤704。由于叶节点总数LC此时已经等于1，因此键索引值K_IDX的解码操作结束，由于键索引值K_IDX此时为5，因此，解码流程所得到的输入键K_IN的最终键索引值K_IDX便为5。

于上述编码操作中，每一笔元数据会记录深度值以及左子树叶节点总数，然而，此仅作为范例说明之用，并未用来作为本发明的限制条件，于另一实施例中，每一笔元数据可更改为记录深度值以及右子树叶节点总数，且解码操作进行相对应修改，亦可同样达到决定出输入键的键索引值的目的，这样的设计变化亦落入本发明的范畴。

关于编码操作，假设键群组所包含的多个键的个数为N以及键的最大长度为M个位，由于键树中每个分支度为2的非叶节点会编码产生一笔元数据(D,NL)，其中深度值D需要log

以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。

【符号说明】

100:电子装置

102:处理电路

104:存储装置

402,404,406,408,410,412,414:编码步骤

702,704,706,708,710,712,714,716:解码步骤

300:键树

K_IN:输入键

ADDR:存储地址

MD:编码数据

K_IDX:键索引值

D_PTR:解码节点位置

LC:叶节点总数

NL:左子树叶节点总数

RL:右子树叶节点总数