A search apparatus (10, 20) comprising: storage means configured to store search target data; and calculation means configured to perform search processing for the search target data based on key data, wherein the search target data stored in the storage means is data of a multiway tree structure including an internal node array and a leaf node array, characterized in that: each internal node in the search target data includes a bit vector representing whether a transition destination is an internal node or a leaf node by a bit, first base information indicating a storing position of an internal node of a transition destination, and second base information indicating a storing position of a leaf node of a transition destination, and wherein the calculation means is configured to repeatedly execute, until a transition node becomes a leaf node, processing of obtaining a chunk of a predetermined bit length from the key data, determining whether a transition destination from the internal node is an internal node or a leaf node based on a bit, in the bit vector of the accessing internal node, that corresponds to a value of the chunk, and when the transition destination determined based on the value of the bit of the bit vector is an internal node, accessing the internal node of the transition destination using the first base information, and when the transition destination is a leaf node, accessing the leaf node of the transition destination using the second base information. storage means configured to store search target data; and calculation means configured to perform search processing for the search target data based on key data, wherein the search target data stored in the storage means is data of a multiway tree structure including an internal node array and a leaf node array, characterized in that: each internal node in the search target data includes a bit vector representing whether a transition destination is an internal node or a leaf node by a bit, first base information indicating a storing position of an internal node of a transition destination, and second base information indicating a storing position of a leaf node of a transition destination, and wherein the calculation means is configured to repeatedly execute, until a transition node becomes a leaf node, processing of obtaining a chunk of a predetermined bit length from the key data, determining whether a transition destination from the internal node is an internal node or a leaf node based on a bit, in the bit vector of the accessing internal node, that corresponds to a value of the chunk, and when the transition destination determined based on the value of the bit of the bit vector is an internal node, accessing the internal node of the transition destination using the first base information, and when the transition destination is a leaf node, accessing the leaf node of the transition destination using the second base information. each internal node in the search target data includes a bit vector representing whether a transition destination is an internal node or a leaf node by a bit, first base information indicating a storing position of an internal node of a transition destination, and second base information indicating a storing position of a leaf node of a transition destination, and wherein the calculation means is configured to repeatedly execute, until a transition node becomes a leaf node, processing of obtaining a chunk of a predetermined bit length from the key data, determining whether a transition destination from the internal node is an internal node or a leaf node based on a bit, in the bit vector of the accessing internal node, that corresponds to a value of the chunk, and when the transition destination determined based on the value of the bit of the bit vector is an internal node, accessing the internal node of the transition destination using the first base information, and when the transition destination is a leaf node, accessing the leaf node of the transition destination using the second base information. obtaining a chunk of a predetermined bit length from the key data, determining whether a transition destination from the internal node is an internal node or a leaf node based on a bit, in the bit vector of the accessing internal node, that corresponds to a value of the chunk, and when the transition destination determined based on the value of the bit of the bit vector is an internal node, accessing the internal node of the transition destination using the first base information, and when the transition destination is a leaf node, accessing the leaf node of the transition destination using the second base information.