Flash memory controller mechanism capable of generating host-based cache information or flash-memory-based cache information to build and optimize binary tree with fewer nodes when cache stores data from host

A flash memory controller, comprising:

• an interface circuit, coupled between a host and an internal bus;
• a read-only memory, coupled to the internal bus, for storing a program code;
• a control logic circuit, coupled between the internal bus and a flash memory module which is externally coupled to the flash memory controller;
• a processor, coupled to the internal bus, for executing the program code to perform access of the flash memory module by using the control logic circuit;
• and
• a cache, coupled to the internal bus, for buffering data corresponding to a plurality of sequential write commands;
• wherein the processor is arranged to build or update a binary tree only when a data amount of data buffered in the cache exceeds data amount of a minimum writing unit within the flash memory module;
• in response to a read command from the host for certain data, the processor is arranged to searching the binary tree to determine whether to access the flash memory module for the certain data;
• after buffered data having the data amount of the minimum writing unit has been written to the flash memory module, the processor deletes one or more nodes from the binary tree without adding new nodes into the binary tree.